期刊
DISCRETE APPLIED MATHEMATICS
卷 233, 期 -, 页码 52-64出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2017.08.014
关键词
Robust optimization; Computational complexity; Approximation algorithms; Selection problem
资金
- National Center for Science (Narodowe Centrum Nauki) [2013/09/B/ST6/01525]
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 0-1 knapsack in which all the item weights are equal to 1. 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. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据