Rectangle packing with one-dimensional resource augmentation

DOI10.1016/j.disopt.2009.04.001zbMath1167.90632OpenAlexW2098775996MaRDI QIDQ834190

Roberto Solis-Oba, Klaus Jansen

Publication date: 19 August 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2009.04.001

zbMATH Keywords

optimizationapproximation algorithmsstrip packingrectangle packing

Mathematics Subject Classification ID

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

Related Items (14)

APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Combinatorial Benders' Cuts for the Strip Packing Problem ⋮ A \((5/3+\varepsilon)\)-approximation for strip packing ⋮ Peak demand minimization via sliced strip packing ⋮ An improved approximation algorithm for scheduling monotonic moldable tasks ⋮ High multiplicity strip packing with three rectangle types ⋮ Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing ⋮ Online square-into-square packing ⋮ TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING ⋮ Improved approximation for two dimensional strip packing with polynomial bounded width ⋮ Complexity and inapproximability results for parallel task scheduling and strip packing ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ New approximability results for two-dimensional bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling parallel jobs to minimize the makespan
• Bin packing can be solved within 1+epsilon in linear time
• Makespan minimization in open shops: A polynomial time approximation scheme
• Two-dimensional bin packing with one-dimensional resource augmentation
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
• On strip packing With rotations
• An asymptotic approximation algorithm for 3D-strip packing
• Approximating the Orthogonal Knapsack Problem for Hypercubes
• Fast Approximation Algorithms for Knapsack Problems
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Algorithm Theory - SWAT 2004
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Mathematical Foundations of Computer Science 2005
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Algorithms and Computation
• Scheduling independent multiprocessor tasks

This page was built for publication: Rectangle packing with one-dimensional resource augmentation