Abstract
An EPTAS (efficient PTAS) is an approximation scheme where ε does not appear in the exponent of n, i.e., the running time is f(ε) n c. We use parameterized complexity to investigate the possibility of improving the known approximation schemes for certain geometric problems to EPTAS. Answering an open question of Alber and Fiala [2], we show that Maximum Independent Set is W[1]-complete for the intersection graphs of unit disks and axis-parallel unit squares in the plane. A standard consequence of this result is that the \(n^{O(1/{\it \epsilon})}\) time PTAS of Hunt et al. [11] for Maximum Independent Set on unit disk graphs cannot be improved to an EPTAS. Similar results are obtained for the problem of covering points with squares.
Research is supported in part by grants OTKA 44733, 42559 and 42706 of the Hungarian National Science Fund.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3-4), 209–218 (1998)
Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134–151 (2004)
Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: FOCS 1996, pp. 2–11. IEEE Comput. Soc. Press, Los Alamitos (1996)
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)
Bazgan, C.: Schémas d’approximation et complexité paramétrée. Technical report, Université Paris Sud (1995)
Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Inform. Process. Lett. 64(4), 165–171 (1997)
Downey, R.G.: Parameterized complexity for the skeptic. In: Proceedings of the 18th IEEE Annual Conference on Computational Complexity, pp. 147–169 (2003)
Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, New York (1999)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: SODA 2001, pp. 671–679. SIAM, Philadelphia (2001)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130–136 (1985)
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238–274 (1998)
Malesińska, E.: Graph-Thoretical Models for Frequency Assignment Problems. PhD thesis, Technical University of Berlin (1997)
Sunil Chandran, L., Grandoni, F.: Refined memorization for vertex cover. Inform. Process. Lett. 93(3), 125–131 (2005)
Wang, D.W., Kuo, Y.-S.: A study on two geometric location problems. Inform. Process. Lett. 28(6), 281–286 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Marx, D. (2005). Efficient Approximation Schemes for Geometric Problems?. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_41
Download citation
DOI: https://doi.org/10.1007/11561071_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29118-3
Online ISBN: 978-3-540-31951-1
eBook Packages: Computer ScienceComputer Science (R0)