An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing

DOI10.1016/S0167-6377(02)00173-6zbMath1013.90132OpenAlexW2053490642MaRDI QIDQ1870001

Vladimir Kotov, Hans Kellerer

Publication date: 4 May 2003

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(02)00173-6

zbMATH Keywords

worst-case analysisbin packingvector packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (16)

Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem ⋮ A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ A two-dimensional vector packing model for the efficient use of coil cassettes ⋮ An optimization-based heuristic for the machine reassignment problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A 4/3-APPROXIMATION ALGORITHM FOR CASSETTE PACKING IN STEEL INDUSTRY ⋮ Automated Credit Rating Prediction in a competitive framework ⋮ Three-Bar Charts Packing Problem ⋮ Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows ⋮ A 4/3 OPT+2/3 approximation for big two-bar charts packing problem ⋮ An improved approximation for packing big two-bar charts ⋮ An efficient algorithm for bin stretching ⋮ Online bin stretching with bunch techniques ⋮ Two dimensional load balancing ⋮ Two-bar charts packing problem ⋮ A branch-and-price algorithm for the two-dimensional vector packing problem

Cites Work

• There is no asymptotic PTAS for two-dimensional vector packing
• Bin packing can be solved within 1+epsilon in linear time
• Resource constrained scheduling as generalized bin packing
• A branch-and-bound algorithm for the two-dimensional vector packing problem
• Lower bounds and algorithms for the 2-dimensional vector packing problem
• Unnamed Item
• Unnamed Item

This page was built for publication: An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing