loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.
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.