There is no asymptotic PTAS for two-dimensional vector packing

DOI10.1016/S0020-0190(97)00179-8MaRDI QIDQ293152zbMATH OpenOpenAlexFDO

Authors 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

analysis of algorithmsbin packingcombinatorial problemsworst-case analysisapproximation schemevector packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing
• Approximation schemes for ordered vector packing problems
• scientific article; zbMATH DE number 1833403
• scientific article; zbMATH DE number 1305407
• Improved Approximation for Vector Bin Packing

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Bin packing can be solved within 1+epsilon in linear time
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Multidimensional Bin Packing Algorithms
• New Algorithms for Bin Packing
• On Packing Two-Dimensional Bins
• On-line and off-line approximation algorithms for vector covering problems
• Resource constrained scheduling as generalized bin packing

Cited in

(26)

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

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

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