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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: July 1998 / Accepted: May 2000¶Published online March 22, 2001
Rights and permissions
About this article
Cite this article
Averbakh, I. On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. 90, 263–272 (2001). https://doi.org/10.1007/PL00011424
Issue Date:
DOI: https://doi.org/10.1007/PL00011424