Name
Abstract | ||
|---|---|---|
In this paper the problem of selecting p items out of n available to minimize the total cost is discussed. This problem is a special case of many important combinatorial optimization problems such as 0-1 knapsack, minimum assignment, single machine scheduling, minimum matroid base or resource allocation. It is assumed that the item costs are uncertain and they are specified as a scenario set containing K distinct cost scenarios. In order to choose a solution the min-max and min-max regret criteria are applied. It is shown that both min-max and min-max regret problems are not approximable within any constant factor unless P=NP, which strengthens the results known up to date. In this paper a deterministic approximation algorithm with performance ratio of O(lnK) for the min-max version of the problem is also proposed. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ipl.2012.10.001 | Inf. Process. Lett. |
Keywords | Field | DocType |
constant factor,item cost,total cost,min-max regret problem,k distinct cost scenario,minimum assignment,items problem,minimum matroid base,important combinatorial optimization problem,min-max regret criterion,min-max version,computational complexity,approximation algorithms,robust optimization,resource allocation | Matroid,Approximation algorithm,Mathematical optimization,Combinatorics,Single-machine scheduling,Regret,Robust optimization,Resource allocation,Knapsack problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
113 | 1-2 | 0020-0190 |
Citations | PageRank | References |
14 | 0.92 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Kasperski | 1 | 352 | 33.64 |
| Adam Kurpisz | 2 | 36 | 3.38 |
| Paweł Zieliński | 3 | 274 | 19.73 |