On the Optimality of Planar and Geometric Approximation Schemes
Dániel Marx · 2007
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 2O(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 2O((1/epsi)1-delta)nO(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 nO(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)nO((1/epsi)1-delta)time PTAS, then ETH fails.