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 条
  • [1] Hardness of Approximation for Knapsack Problems
    Buhrman, Harry
    Loff, Bruno
    Torenvliet, Leen
    THEORY OF COMPUTING SYSTEMS, 2015, 56 (02) : 372 - 393
  • [2] Approximation for knapsack problems with multiple constraints
    Zhang L.
    Zhang Y.
    Journal of Computer Science and Technology, 1999, 14 (4) : 289 - 297
  • [3] HARDNESS OF APPROXIMATION FOR QUANTUM PROBLEMS
    Gharibian, Sevag
    Kempe, Julia
    QUANTUM INFORMATION & COMPUTATION, 2014, 14 (5-6) : 517 - 540
  • [4] Approximation algorithms for knapsack problems with cardinality constraints
    Caprara, A
    Kellerer, H
    Pferschy, U
    Pisinger, D
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 123 (02) : 333 - 345
  • [5] Approximation of knapsack problems with conflict and forcing graphs
    Pferschy, Ulrich
    Schauer, Joachim
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) : 1300 - 1323
  • [6] Approximation of knapsack problems with conflict and forcing graphs
    Ulrich Pferschy
    Joachim Schauer
    Journal of Combinatorial Optimization, 2017, 33 : 1300 - 1323
  • [7] Approximation schemes for knapsack problems with shelf divisions
    Xavier, EC
    Miyazawa, FK
    THEORETICAL COMPUTER SCIENCE, 2006, 352 (1-3) : 71 - 84
  • [8] Hardness of Approximation for H-free Edge Modification Problems
    Bliznets, Ivan
    Cygan, Marek
    Komosa, Pawel
    Pilipczuk, Michal
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2018, 10 (02)
  • [9] Approximation Hardness for A Class of Sparse Optimization Problems
    Chen, Yichen
    Ye, Yinyu
    Wang, Mengdi
    JOURNAL OF MACHINE LEARNING RESEARCH, 2019, 20
  • [10] Approximation for multi-knapsack problem
    Zhang, LA
    Li, LY
    Huang, X
    CHINESE SCIENCE BULLETIN, 1996, 41 (12): : 1042 - 1045
12345