TY - GEN
T1 - Approximation algorithms for maximum independent set of pseudo-disks
AU - Chan, Timothy M.
AU - Har-Peled, Sariel
PY - 2009
Y1 - 2009
N2 - We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, that leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
AB - We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, that leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
KW - Approximation
KW - Local search
UR - http://www.scopus.com/inward/record.url?scp=70849095487&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70849095487&partnerID=8YFLogxK
U2 - 10.1145/1542362.1542420
DO - 10.1145/1542362.1542420
M3 - Conference contribution
AN - SCOPUS:70849095487
SN - 9781605585017
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 333
EP - 340
BT - Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
T2 - 25th Annual Symposium on Computational Geometry, SCG'09
Y2 - 8 June 2009 through 10 June 2009
ER -