On the complexity of anchored rectangle packing

DOI10.4230/LIPIcs.ESA.2019.8OpenAlexW2977596275MaRDI QIDQ5075741

Antonios Foivos Antoniadis, Peter Kling, Christoph Damerius, Ruben Hoeksma, Felix Biermeier, Andrés Cristi, Lukas Nölke, Dominik Kaaser

Publication date: 11 May 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2019.8

zbMATH Keywords

hardnessPTASrectangle packingresource augmentationNPanchored rectangle

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Packing anchored rectangles
• On covering problems of Rado
• Anchored rectangle and square packings
• Face covers and the genus problem for apex graphs
• MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS
• Multicommodity demand flow in a tree and packing integer programs
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Maximum Area Axis-Aligned Square Packings.
• How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
• A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem
• Improved Approximation Algorithm for Two-Dimensional Bin Packing
• Some Covering Theorems (III)
• Some Covering Theorems (I)
• Some Covering Theorems (II)

This page was built for publication: On the complexity of anchored rectangle packing