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
TypeCommunication / Conférence
Conference titleIEEE International Conference on Services Systems and Services Management (ICSSSM'06)
Book titleInternational Conference on Services Systems and Services Management (ICSSSM'06) Proceedings
MetadataShow full item record
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 / Keywordsknapsack; Robust knapsack problem
Showing items related by title and author.
Kalaï, Rim; Aloulou, Mohamed Ali; Vallin, Philippe; Vanderpooten, Daniel (Université Paris-DauphineParis, 2006) Document de travail / Working paper