48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) On the Optimality of Planar and Geometric Approximation Schemes Providence, Rhode Island October 21-October 23 ISBN: 0-7695-3010-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.26
We show for several planar and geometric problems that the best known approximation schemes are essentially optimal with respect to the dependence on \varepsilon. For example, we show that the 2^{{\rm O}(1/ \in )} \cdot n time approximation schemes for planar MAXIMUM INDEPENDENT SET and for TSP on a metric defined by a planar graph are essentially optimal: if there is a 2^{{\rm O}(1/ \in )} \cdot n such that any of these problems admits a 2^{{\rm O}((1/ \in )1 - \delta )} n^{{\rm O}(1)} time PTAS, then the Exponential Time Hypothesis (ETH) fails. It is known that MAXIMUM INDEPENDENT SET on unit disk graphs and the planar logic problems MPSAT, TMIN, TMAX admit n^{{\rm O}(1/ \in )} time approximation schemes. We show that they are optimal in the sense that if there is a \delta \le 0 such that any of these problems admits a 2^{(1/ \in )^{{\rm O}(1)} } n^{{\rm O}((1/ \in )1 - \delta )} time PTAS, then ETH fails.
Citation:
Dániel Marx, "On the Optimality of Planar and Geometric Approximation Schemes," focs, pp.338-348, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||