Hardness of Approximation for Knapsack Problems

被引：0
作者：
Harry Buhrman
Bruno Loff
Leen Torenvliet
机构：
[1] CWI,ILLC
[2] University of Amsterdam,undefined
来源：
Theory of Computing Systems | 2015年 / 56卷
关键词：
Computational complexity; Knapsack problem; Subset-sum; Exponential-time hypothesis; PRAM without bit operations; Algebraic-circuit lower-bounds; Hardness of approximation;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We show various hardness results for knapsack and related problems; in particular we will show that unless the Exponential-Time Hypothesis is false, subset-sum cannot be approximated any better than with an FPTAS. We also provide new unconditional lower bounds for approximating knapsack in Ketan Mulmuley’s parallel PRAM model. Furthermore, we give a simple new algorithm for approximating knapsack and subset-sum, that can be adapted to work for small space, or in small parallel time.
引用
收藏
页码：372 / 393
页数：21
相关论文
共 50 条
12345