期刊
INFORMATION PROCESSING LETTERS
卷 110, 期 16, 页码 707-710出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2010.05.031
关键词
Two-dimensional knapsack; Efficient polynomial-time approximation; schemes; Parameterized complexity; Theory of computation
资金
- Technion V.P.R. Fund
In the d-dimensional (vector) knapsack problem given is a set of items, each having a d-dimensional size vector and a profit, and a d-dimensional bin. The goal is to select a subset of the items of maximum total profit such that the sum of all vectors is bounded by the bin capacity in each dimension. It is well known that, unless P = NP, there is no fully polynomial-time approximation scheme for d-dimensional knapsack, already for d = 2. The best known result is a polynomial-time approximation scheme (PEAS) due to Frieze and Clarke [A.M. Frieze, M. Clarke, Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European J. Operat. Res. 15 (1) (1984) 100-109] for the case where d >= 2 is some fixed constant. A fundamental open question is whether the problem admits an efficient PEAS (EPTAS). In this paper we resolve this question by showing that there is no EPTAS for d-dimensional knapsack, already for d = 2, unless W[1] = FPT. Furthermore, we show that unless all problems in SNP are solvable in sub-exponential time, there is no approximation scheme for two-dimensional knapsack whose running time is f(1/epsilon)vertical bar I vertical bar(0(root 1/epsilon)), for any function f. Together, the two results suggest that a significant improvement over the running time of the scheme of Frieze and Clarke is unlikely to exist. (C) 2010 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据