Hardness of approximation for knapsack problems

DOI10.1007/S00224-014-9550-ZMaRDI QIDQ2345987zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algebraic-circuit lower-boundscomputational complexityexponential-time hypothesishardness of approximationknapsack problemPRAM without bit operationssubset-sum

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

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

Cites work

• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An Optimal Parallel Algorithm for Formula Evaluation
• Bottleneck Problems and Dynamic Programming
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Computing Partitions with Applications to the Knapsack Problem
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• Knapsack problems in groups
• Lower Bounds in a Parallel Model without Bit Operations
• On problems as hard as CNF-SAT
• On the complexity of k-SAT
• Reducing a target interval to a few exact queries
• Saving space by algebraization
• Some optimal inapproximability results
• Which problems have strongly exponential complexity?

Cited in

(6)

• Solutions of hard knapsack problems using extreme pruning
• Constant-time approximation algorithms for the knapsack problem
• scientific article; zbMATH DE number 1408349 (Why is no real title available?)
• Hard Equality Constrained Integer Knapsacks
• No polynomial kernels for knapsack
• Classical and quantum algorithms for variants of subset-sum via dynamic programming

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)