On approximating maximum independent set of rectangles

DOI10.1109/FOCS.2016.92MaRDI QIDQ6946414zbMATH OpenFDO

Authors Alina Ene, Julia Chuzhoy

Publication date 6 August 2025

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

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(5)

• Approximation of MWIS on geometric intersection graphs
• Learning-augmented maximum independent set
• Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
• Parameterized approximation for maximum weight independent set of rectangles and segments
• Dynamic streaming algorithms for geometric independent set

This page was built for publication: On approximating maximum independent set of rectangles

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