Name
Abstract | ||
|---|---|---|
In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 01 knapsack in which all the item weights are equal to1. Its deterministic version has an O(n)-time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2017.08.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Robust optimization,Computational complexity,Approximation algorithms,Selection problem | Combinatorics,Mathematical optimization,Knapsack problem,Total cost,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
abs/1505.06893 | C | 0166-218X |
Citations | PageRank | References |
5 | 0.48 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Kasperski | 1 | 352 | 33.64 |
| Paweł Zieliński | 2 | 227 | 28.62 |