There is no asymptotic PTAS for two-dimensional vector packing

DOI10.1016/S0020-0190(97)00179-8zbMATH Open1338.68122OpenAlexW2117812463MaRDI QIDQ293152FDOQ293152

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

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

zbMATH Keywords

analysis of algorithmsbin packingcombinatorial problemsworst-case analysisapproximation schemevector packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (25)

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

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)