Approximation schemes for maximum weight independent set of rectangles

DOI10.1109/FOCS.2013.50MaRDI QIDQ6981735zbMATH OpenFDO

Authors Andreas Wiese, Anna Adamaszek

Publication date 20 May 2025

Full work available at URL https://doi.org/10.1109/FOCS.2013.50

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(9)

• Approximation of MWIS on geometric intersection graphs
• Geometric covering via extraction theorem
• Recognizing integrality of weighted rectangles partitions
• 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
• On greedily packing anchored rectangles
• Parameterized approximation for maximum weight independent set of rectangles and segments
• An improved guillotine cut for squares
• Covering simple orthogonal polygons with rectangles

This page was built for publication: Approximation schemes for maximum weight independent set of rectangles

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