Thumbnail - Request a copy

Lexicographic alpha-robust knapsack problems: complexity results

Vanderpooten, Daniel; Kalaï, Rim (2006), Lexicographic alpha-robust knapsack problems: complexity results, International Conference on Services Systems and Services Management (ICSSSM'06) Proceedings, IEEE. http://dx.doi.org/10.1109/ICSSSM.2006.320662

Type
Communication / Conférence
Date
2006
Conference title
IEEE International Conference on Services Systems and Services Management (ICSSSM'06)
Conference date
2006-10
Conference city
Troyes
Conference country
France
Book title
International Conference on Services Systems and Services Management (ICSSSM'06) Proceedings
Publisher
IEEE
ISBN
1-4244-0450-9
Publication identifier
Metadata
Show full item record
Author(s)
Vanderpooten, Daniel
Kalaï, Rim
Abstract (EN)
The knapsack problem is a classical combinatorial problem used to model many industrial situations. Faced with uncertainty on the model parameters, robustness analysis is an appropriate approach to find reliable solutions. The robust knapsack problem was studied in the literature using a max-min criterion. In this paper, we show the drawbacks of this criterion and propose a new robustness approach, called lexicographic α-robustness. We show that the complexity of the lexicographic α-robust problem does not increase compared with the max-min version and present a pseudo-polynomial algorithm in the case of a bounded number of scenarios.
Subjects / Keywords
knapsack; Robust knapsack problem