On the Optimality of Planar and Geometric Approximation Schemes

We show for several planar and geometric problems that the best known approximation schemes are essentially optimal with respect to the dependence on epsi. For example, we show that the 2^O(1/epsi)ldrn time approximation schemes for planar maximum independent set and for TSP on a metric defined bv a planar graph are essentially optimal: if there is a delta>0 such that any of these problems admits a 2^{O((1/epsi) 1-delta )}n^O(1) time PTAS, then the exponential tune hypothesis (ETH) fails. It is known that maximum independent set on unit disk graphs and the planar logic problems MPSAT. TMIN, TMAX admit n^O(1/epsi) time approximation schemes. We show that they are optimal in the sense that if there is a delta>0 such that any of these problems admits a 2^{(1/epsi) O(1)} n^{O((1/epsi) 1-delta )} time PTAS, then ETH fails.