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