Approximation Algorithms for Maximum Independent Set of
Pseudo-Disks
Timothy M. Chan and
Sariel Har-Peled.
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.