Approximating maximum independent set for rectangles in the plane

DOI10.1109/FOCS52979.2021.00042MaRDI QIDQ6943510zbMATH OpenFDO

Authors Joseph S. B. Mitchell

Publication date 13 August 2025

Full work available at URL https://doi.org/10.1109/FOCS52979.2021.00042

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited in

(17)

• Approximation of MWIS on geometric intersection graphs
• Approximation schemes for geometric knapsack for packing spheres and fat objects
• Set cover, hitting set, and independent set problems for some restricted classes of geometric objects
• A 1.9999-approximation algorithm for vertex cover on string graphs
• Approximating the maximum independent set of convex polygons with a bounded number of directions
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Tight approximation algorithms for 2D guillotine strip packing
• On some geometric optimization problems with segments
• Approximation algorithms for round-UFP and round-SAP
• Segment proximity graphs and nearest neighbor queries amid disjoint segments
• Parameterized approximation for maximum weight independent set of rectangles and segments
• Random-order online independent set of intervals and hyperrectangles
• On approximation schemes for stabbing rectilinear polygons
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Segment proximity graphs and nearest neighbor queries amid disjoint segments
• Dynamic streaming algorithms for geometric independent set
• Covering simple orthogonal polygons with rectangles

This page was built for publication: Approximating maximum independent set for rectangles in the plane

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