Name
Abstract | ||
|---|---|---|
The knapsack problem is a classical combinatorial optimization problem used to model many industrial situations. The robust version of this problem was studied in the literature using a max-min or min-max regret criterion. In this paper, we show the drawbacks of such criteria and propose a new robustness approach, called lexicographic alpha-robustness. We show that the complexity of the lexicographic alpha-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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1111/j.1475-3995.2010.00786.x | INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH |
Keywords | Field | DocType |
uncertainty, robustness, 0-1 knapsack problem, min-max (regret), complexity | Mathematical optimization,Change-making problem,Generalized assignment problem,Robustness (computer science),Continuous knapsack problem,Cutting stock problem,Knapsack problem,Lexicographical order,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
18 | 1 | 0969-6016 |
Citations | PageRank | References |
2 | 0.38 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rim Kalaï | 1 | 22 | 1.48 |
| Daniel Vanderpooten | 2 | 1153 | 74.66 |