Hardness of approximation for knapsack problems
DOI10.1007/S00224-014-9550-ZzbMATH Open1328.68073OpenAlexW2125990029MaRDI QIDQ2345987FDOQ2345987
Authors: Harry Buhrman, Bruno Loff, Leen Torenvliet 
Publication date: 29 May 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/24129
Recommendations
- Parallel approximation schemes for subset sum and knapsack problems
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- Constant-time approximation algorithms for the knapsack problem
- Approximation for knapsack problems with multiple constraints
- Approximation for multi-knapsack problem
computational complexityknapsack problemhardness of approximationexponential-time hypothesissubset-sumalgebraic-circuit lower-boundsPRAM without bit operations
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Which problems have strongly exponential complexity?
- Title not available (Why is that?)
- Title not available (Why is that?)
- On problems as hard as CNF-SAT
- Some optimal inapproximability results
- On the complexity of \(k\)-SAT
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Title not available (Why is that?)
- Title not available (Why is that?)
- Knapsack problems in groups
- Computing Partitions with Applications to the Knapsack Problem
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Reducing a target interval to a few exact queries
- An Optimal Parallel Algorithm for Formula Evaluation
- Saving space by algebraization
- Bottleneck Problems and Dynamic Programming
- Lower Bounds in a Parallel Model without Bit Operations
Cited In (4)
This page was built for publication: Hardness of approximation for knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345987)
