Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

Details Approximation Algorithms for Maximum Independent Set of Pseudo-Disks Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

2011-03-08

arxiv.org/abs/1103.1431v1

Computer Science

Computational Geometry

Scientific paper

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, which 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.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Maximum Independent Set of Pseudo-Disks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Maximum Independent Set of Pseudo-Disks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Maximum Independent Set of Pseudo-Disks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-81972