TY - GEN
T1 - Quasi-polynomial time approximation scheme for sparse subsets of polygons
AU - Har-Peled, Sariel
PY - 2014
Y1 - 2014
N2 - We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese [1, 2] to polygons of arbitrary com-plexity. Surprisingly, the algorithm also works for computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length 4 (i.e., K2,2).
AB - We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese [1, 2] to polygons of arbitrary com-plexity. Surprisingly, the algorithm also works for computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length 4 (i.e., K2,2).
KW - Approximation algorithms
KW - Independent set
KW - QPTAS
UR - http://www.scopus.com/inward/record.url?scp=84904438570&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904438570&partnerID=8YFLogxK
U2 - 10.1145/2582112.2582157
DO - 10.1145/2582112.2582157
M3 - Conference contribution
AN - SCOPUS:84904438570
SN - 9781450325943
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 120
EP - 129
BT - Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014
PB - Association for Computing Machinery
T2 - 30th Annual Symposium on Computational Geometry, SoCG 2014
Y2 - 8 June 2014 through 11 June 2014
ER -