A Polynomial Time Approximation Scheme for the Square Packing Problem

DOI10.1007/978-3-540-68891-4_13MaRDI QIDQ3503847zbMATH OpenOpenAlexFDO

Authors Roberto Solis-Oba, Klaus Jansen

Publication date 10 June 2008

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68891-4_13

Mathematics Subject Classification ID

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

Recommendations

• Packing squares with profits
• An approximation algorithm for square packing.
• On rectangle packing, maximizing benefits
• Maximizing the total profit of rectangles packed into a rectangle
• New Approximability Results for 2-Dimensional Packing Problems

Cites work

• scientific article; zbMATH DE number 1226257 (Why is no real title available?)
• A near-optimal solution to a two-dimensional cutting stock problem
• An efficient approximation for the generalized assignment problem
• Approximating the Orthogonal Knapsack Problem for Hypercubes
• Fast Approximation Algorithms for Knapsack Problems
• Mathematical Foundations of Computer Science 2005
• Maximizing the total profit of rectangles packed into a rectangle
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Two-dimensional bin packing with one-dimensional resource augmentation

Cited in

(21)

• Mathematical Foundations of Computer Science 2005
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• An algorithm for packing squares
• scientific article; zbMATH DE number 21366 (Why is no real title available?)
• Approximation algorithms for orthogonal packing problems for hypercubes
• Packing squares with profits
• 2D knapsack: packing squares
• On the two-dimensional knapsack problem for convex polygons
• Approximation and online algorithms for multidimensional bin packing: a survey
• On packing rectangles with resource augmentation: maximizing the profit
• Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
• On guillotine separable packings for the two-dimensional geometric knapsack problem
• An approximation algorithm for square packing.
• Breaking the barrier of 2 for the storage allocation problem
• On the two-dimensional knapsack problem for convex polygons
• Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
• Two dimensional knapsack with unloading constraints
• Two for One: Tight Approximation of 2D Bin Packing
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• 2D knapsack: packing squares

This page was built for publication: A Polynomial Time Approximation Scheme for the Square Packing Problem

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