Treffer: Approximating the min–max (regret) selecting items problem

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 , which strengthens the results known up to date. In this paper a deterministic approximation algorithm with performance ratio of for the min–max version of the problem is also proposed. [Copyright &y& Elsevier]

Copyright of Information Processing Letters is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)