TY - GEN

T1 - Approximation algorithms for Polynomial-Expansion and Low-Density graphs

AU - Har-Peled, Sariel

AU - Quanrud, Kent

N1 - Funding Information:
Work on this paper was partially supported by a NSF AF awards CCF-1421231, and CCF-1217462.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Computational geometry

KW - Hardness of approximation

KW - SETH

UR - http://www.scopus.com/inward/record.url?scp=84945583838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945583838&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48350-3_60

DO - 10.1007/978-3-662-48350-3_60

M3 - Conference contribution

AN - SCOPUS:84945583838

SN - 9783662483497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 717

EP - 728

BT - Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings

A2 - Bansal, Nikhil

A2 - Finocchi, Irene

PB - Springer

T2 - 23rd European Symposium on Algorithms, ESA 2015

Y2 - 14 September 2015 through 16 September 2015

ER -