Approximation algorithms for Polynomial-Expansion and Low-Density graphs

Sariel Har-Peled, Kent Quanrud

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

Abstract

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, and includes planar graphs. This family of graphs has some interesting properties, and in particular, it is a subset of the family of graphs that have polynomial expansion. We present efficient (1+ε)-approximation algorithms for polynomial expansion graphs, for Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTAS’s for these problems are known for subclasses of this graph family. These results have immediate interesting applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth.

Original languageEnglish (US)
Title of host publicationAlgorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
EditorsNikhil Bansal, Irene Finocchi
PublisherSpringer-Verlag
Pages717-728
Number of pages12
ISBN (Print)9783662483497
DOIs
StatePublished - Jan 1 2015
Event23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece
Duration: Sep 14 2015Sep 16 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9294
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other23rd European Symposium on Algorithms, ESA 2015
CountryGreece
CityPatras
Period9/14/159/16/15

Keywords

  • Computational geometry
  • Hardness of approximation
  • SETH

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximation algorithms for Polynomial-Expansion and Low-Density graphs'. Together they form a unique fingerprint.

  • Cite this

    Har-Peled, S., & Quanrud, K. (2015). Approximation algorithms for Polynomial-Expansion and Low-Density graphs. In N. Bansal, & I. Finocchi (Eds.), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings (pp. 717-728). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer-Verlag. https://doi.org/10.1007/978-3-662-48350-3_60