There is no asymptotic PTAS for two-dimensional vector packing

DOI10.1016/S0020-0190(97)00179-8zbMath1338.68122OpenAlexW2117812463MaRDI QIDQ293152

Gerhard J. Woeginger

Publication date: 9 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097001798?np=y

zbMATH Keywords

combinatorial problemsanalysis of algorithmsworst-case analysisbin packingapproximation schemevector packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (23)

Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem ⋮ A two-dimensional vector packing model for the efficient use of coil cassettes ⋮ Vector bin packing with heterogeneous bins: application to the machine reassignment problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs ⋮ On data reduction for dynamic vector bin packing ⋮ There is no APTAS for 2-dimensional vector bin packing: revisited ⋮ A 4/3-APPROXIMATION ALGORITHM FOR CASSETTE PACKING IN STEEL INDUSTRY ⋮ Approximation schemes for generalized two-dimensional vector packing with application to data placement ⋮ A 4/3 OPT+2/3 approximation for big two-bar charts packing problem ⋮ Bin covering with cardinality constraints ⋮ Set Covering with Ordered Replacement: Additive and Multiplicative Gaps ⋮ Colocating tasks in data centers using a side-effects performance model ⋮ Structure of polynomial-time approximation ⋮ Lower bounds and algorithms for the 2-dimensional vector packing problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bin packing with controllable item sizes ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Hardness of approximation for orthogonal rectangle packing and covering problems ⋮ A branch-and-price algorithm for the two-dimensional vector packing problem ⋮ Truthful mechanism design for bin packing with applications on cloud computing ⋮ An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing

Cites Work

• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Bin packing can be solved within 1+epsilon in linear time
• Resource constrained scheduling as generalized bin packing
• On-line and off-line approximation algorithms for vector covering problems
• New Algorithms for Bin Packing
• On Packing Two-Dimensional Bins
• Multidimensional Bin Packing Algorithms

This page was built for publication: There is no asymptotic PTAS for two-dimensional vector packing