Paper Info
Title
On the complexity of a class of combinatorial optimization problems with uncertainty
Abstract
.   We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})2 m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty.
Year
DOI
Venue
2001
10.1007/PL00011424
Math. Program.
Keywords
Field
DocType
Key words: polynomial algorithm – complexity – robust optimization
Discrete mathematics,Mathematical optimization,Finite set,Combinatorial optimization problem,Robustness (computer science),Combinatorial optimization,Polynomial algorithm,Mathematics,Polynomial method
Journal
Volume
Issue
ISSN
90
2
0025-5610
Citations 
PageRank 
References 
87
7.58
3
Authors
1
Name
Order
Citations
PageRank
Igor Averbakh169954.76