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 -