There is no EPTAS for two-dimensional knapsack

DOI10.1016/j.ipl.2010.05.031zbMath1234.68153WikidataQ56050295 ScholiaQ56050295MaRDI QIDQ765522

Ariel Kulik, Hadas Shachnai

Publication date: 19 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.05.031

zbMATH Keywords

theory of computation; parameterized complexity; efficient polynomial-time approximation schemes; two-dimensional knapsack

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION, An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Approximate composable truthful mechanism design, Approximation schemes for deal splitting and covering integer programs with multiplicity constraints, A randomized heuristic repair for the multidimensional knapsack problem, On the optimality of exact and approximation algorithms for scheduling problems, Parameterized approximation via fidelity preserving transformations, Network pollution games, A PTAS for a class of binary non-linear programs with low-rank functions, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem, On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns, Approximating multidimensional subset sum and Minkowski decomposition of polygons, Approximation and online algorithms for multidimensional bin packing: a survey, Knapsack problems: a parameterized point of view, Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Optimization, approximation, and complexity classes
• A new fully polynomial time approximation scheme for the Knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Parametrized complexity theory.
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Linear FPT reductions and computational lower bounds
• A Note on Approximation Schemes for Multidimensional Knapsack Problems