There is no EPTAS for two-dimensional knapsack

DOI10.1016/J.IPL.2010.05.031MaRDI QIDQ765522zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

parameterized complexitytheory of computationefficient 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)

Recommendations

• Faster approximation schemes for the two-dimensional knapsack problem
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
• There is no asymptotic PTAS for two-dimensional vector packing
• A faster FPTAS for knapsack problem with cardinality constraint

Cites work

• scientific article; zbMATH DE number 3850828 (Why is no real title available?)
• scientific article; zbMATH DE number 3705908 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• A new fully polynomial time approximation scheme for the Knapsack problem
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for knapsack problems with cardinality constraints
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Linear FPT reductions and computational lower bounds
• Optimization, approximation, and complexity classes
• Parameterized approximation scheme for the multiple knapsack problem
• Parametrized complexity theory.

Cited in

(18)

• Faster approximation schemes for the two-dimensional knapsack problem
• A randomized heuristic repair for the multidimensional knapsack problem
• Bounding the running time of algorithms for scheduling and packing problems
• An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
• Two approximation schemes for scheduling on parallel machines under a grade of service provision
• Network pollution games
• 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
• On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns
• Approximate composable truthful mechanism design
• Improved approximation for two-dimensional vector multiple knapsack
• A PTAS for a class of binary non-linear programs with low-rank functions
• Parameterized approximation via fidelity preserving transformations
• Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
• An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion
• On the optimality of exact and approximation algorithms for scheduling problems
• Approximate truthful mechanism design for two-dimensional orthogonal knapsack problem

Describes a project that uses

Uses Software

• Knapsack

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765522)