Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2719))
Included in the following conference series:
2031Accesses
Abstract
We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST by adapting techniques used previously for approximating TSP. Givenn points in the plane,d = 2 or 3, and∈ > 0, the scheme finds an approximation with cost within 1 +∈ of the lowest cost spanning tree with the property that all nodes have degree at mostd. We also develop a polynomial time approximation scheme for the Euclidean version of the Red-Blue Separation Problem.
Supported by David and Lucille Packard Fellowship, and NSF Grants CCR-0098180 and CCR-009818. Work done partially while visiting the CS Dept at UC Berkeley.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Polynomial-time approximation schemes for Euclidean TSP and other geometric problems.Proceedings of 37th IEEE Symp. on Foundations of Computer Science, 1996.
S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems.JACM45(5) 753–782, 1998.
S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey.Math Programming, 2003 (to appear). Available from www.cs.princeton.edu/~arora.
S. Arora and G. Karakostas. Approximation schemes for minimum latency problems.Proc. ACM Symposium on Theory of Computing, 1999.
S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the Euclideank-medians and related problems. InProc. 30th ACM Symposium on Theory of Computing, pp 106–113, 1998.
J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points.Proc. Cambridge Philos. Soc.55:299–327, 1959.
M. Bern and D. Eppstein. Approximation algorithms for geometric problems. In [9].
A. Czumaj and A. Lingas. A polynomial time approximation scheme for Euclidean minimum costk-connectivity.Proc. 25th Annual International Colloquium on Automata, Languages and Programming, LNCS, Springer Verlag 1998.
D. Hochbaum, ed. Approximation Algorithms for NP-hard problems. PWS Publishing, Boston, 1996.
S. Khuller, B. Raghavachari, and N. Young. Low degree spanning tree of small weight.SIAM J. Computing,25:355–368, 1996. Preliminary version inProc. 26th ACM Symposium on Theory of Computing, 1994.
S. G. Kolliopoulos and S. Rao. A nearly linear time approximation scheme for the Euclideank-median problem.LNCS, vol.1643, pp 378–387, 1999.
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys. The traveling salesman problem. John Wiley, 1985
C.S. Mata and J. Mitchell. Approximation Algorithms for Geometric tour and network problems. InProc. 11th ACM Symp. Comp. Geom., pp 360–369, 1995.
J. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple PTAS for geometrick-MST, TSP, and related problems.SIAM J. Comp.,28, 1999. Preliminary manuscript, April 30, 1996. To appear inSIAM J. Computing.
C. H. Papadimitriou and U. V. Vazirani. On two geometric problems related to the traveling salesman problem.J. Algorithms5(1984), pp. 231–246.
B. Raghavachari. Algorithms for finding low degree structures. In [9]
S. Rao and W. Smith. Approximating geometric graphs via “spanners” and “banyans.” InProc. 30th ACM Symposium on Theory of Computing, pp. 540–550, 1998.
Author information
Authors and Affiliations
Princeton University, Princeton, NJ
Sanjeev Arora
Yale University, New Haven, CT
Kevin L. Chang
- Sanjeev Arora
You can also search for this author inPubMed Google Scholar
- Kevin L. Chang
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Dept. of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands
Jos C. M. Baeten
School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA, 30332-0205, USA
Jan Karel Lenstra
Department of Information Technology, Uppsala University, P.O. Box 337, 75105, Uppsala, Sweden
Joachim Parrow
Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE, Enschede, The Netherlands
Gerhard J. Woeginger
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arora, S., Chang, K.L. (2003). Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol 2719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45061-0_16
Download citation
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative