There is no EPTAS for two-dimensional knapsack

DOI10.1016/j.ipl.2010.05.031zbMath1234.68153OpenAlexW2067088693WikidataQ56050295 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 computationparameterized complexityefficient polynomial-time approximation schemestwo-dimensional knapsack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (16)

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

Uses Software

• Knapsack

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: There is no EPTAS for two-dimensional knapsack