TY - GEN
T1 - Approximating Maximum Independent Set for Rectangles in the Plane
AU - Mitchell, Joseph S.B.
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is O(log log n). The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.
AB - We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is O(log log n). The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.
KW - approximation
KW - independent set
KW - rectangles
UR - https://www.scopus.com/pages/publications/85127174081
U2 - 10.1109/FOCS52979.2021.00042
DO - 10.1109/FOCS52979.2021.00042
M3 - Conference contribution
AN - SCOPUS:85127174081
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 339
EP - 350
BT - Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PB - IEEE Computer Society
T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Y2 - 7 February 2022 through 10 February 2022
ER -