Approximation algorithms for maximum independent set of pseudo-disks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
Pages333-340
Number of pages8
DOIs
StatePublished - 2009
Event25th Annual Symposium on Computational Geometry, SCG'09 - Aarhus, Denmark
Duration: Jun 8 2009Jun 10 2009

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other25th Annual Symposium on Computational Geometry, SCG'09
Country/TerritoryDenmark
CityAarhus
Period6/8/096/10/09

Keywords

  • Approximation
  • Local search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Approximation algorithms for maximum independent set of pseudo-disks'. Together they form a unique fingerprint.

Cite this