On the complexity of a class of combinatorial optimization problems with uncertainty

On the complexity of a class of combinatorial optimization problems with uncertainty

0.00 Avg rating0 Votes
Article ID: iaor2002923
Country: Germany
Volume: 90
Issue: 2
Start Page Number: 263
End Page Number: 272
Publication Date: Jan 2001
Journal: Mathematical Programming
Authors:
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})2m) 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 represntation of uncertainty.

Reviews

Required fields are marked *. Your email address will not be published.