Abstract
In the b-degree constrained Euclidean minimum spanning tree problem (bMST) we are given n points in [0,1]d and a degree constraint b ≥ 2. The aim is to find a minimum weight spanning tree in which each vertex has degree at most b. In this paper we analyze the probabilistic version of the problem and prove in affirmative the conjecture of Yukich stated in 1998 on the asymptotics of the problem for uniformly (and also some non-uniformly) distributed points in [0,1]d: the optimal length L bMST (X 1,...,X n ) of a b-degree constrained minimal spanning tree on X 1,...,X n given by iid random variables with values in [0,1]d satisfies
where α(L bMST ,d) is a positive constant, f is the density of the absolutely continuous part of the law of X 1 and c.c. stands for complete convergence. In the case b = 2, the b-degree constrained MST has the same asymptotic behavior as the TSP, and we have α(L bMST ,d) = α(L TSP ,d). We also show concentration of L bMST around its mean and around . The result of this paper may spur further investigation of probabilistic spanning tree problems with degree constraints.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Journal of the ACM 45(5), 754–782 (1998)
Arora, S., Chang, K.: Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica 40(3), 189–210 (2004)
Baltz, A., Dubhashi, D., Srivastav, A., Tansini, L., Werth, S.: Probabilistic analysis of a multidepot vehicle routing problem. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, Springer, Heidelberg (2005), and in Random Structures and Algorithms, 30(1-2), 206–225 (2007)
Beardwood, J., Halton, J.H., Hammersley, J.M.: The shortest path through many points. Proceedings of the Cambridge Philosophical Society 55, 299–327 (1959)
Chan, T.M.: Euclidean bounded-degree spanning tree ratios. In: Proceedings of the 19th ACM Symposium on Computational Geometry, pp. 11–19. ACM Press, New York (2003)
Dumitrescu, A., Tóth, C.D.: Light orthogonal networks with constant geometric dilation. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 175–187. Springer, Heidelberg (2007)
Hammersley, J.M.: Postulates for subadditive processes. Annals of Probability 2, 652–680 (1974)
McGivney, K., Yukich, J.E.: Asymptotics for geometric location problems over random samples. Advances in Applied Probability 31, 632–642 (1999)
Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Discrete & Computational Geometry 8(3), 265–293 (1992)
Papadimitriou, C.H.: The probabilistic analysis of matching heuristics. In: Proceedings of the 15th Allerton Conference on Communication, Control and Computing, pp. 368–378 (1978)
Papadimitriou, C.H., Vazirani, U.V.: On two geometric problems related to the travelling salesman problem. Journal of Algorithms 5(2), 231–246 (1984)
Raghavachari, B.: Algorithms for finding low degree structures. In: Hochbaum, D. (ed.) Approximation algorithms, pp. 266–295. PWS Publishers Inc. (1996)
Redmond, C., Yukich, J.E.: Limit theorems and rates of convergence for Euclidean functionals. Annals of Applied Probability 4(4), 1057–1073 (1994)
Rhee, W.T.: A matching problem and subadditive Euclidean functionals. Annals of Applied Probability 3(3), 794–801 (1993)
Steele, J.M.: Subadditive Euclidean functionals and non-linear growth in geometric probability. Annals of Probability 9, 365–376 (1981)
Steele, J.M.: Probability theory and combinatorial optimization. In: CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, vol. 69 (1997)
Strassen, V.: The existence of probability measures with given marginals. Annals of Mathematical Statistics 36, 423–439 (1965)
Weide, B.: Statistical methods in algorithm design and analysis, Ph.D. thesis, Computer Science Department, Carnegie Mellon University (1978)
Yukich, J.E.: Probability theory of classical Euclidean optimization problems. Lecture Notes in Mathematics, vol. 1675. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Srivastav, A., Werth, S. (2007). Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem. In: Arvind, V., Prasad, S. (eds) FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2007. Lecture Notes in Computer Science, vol 4855. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77050-3_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-77050-3_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77049-7
Online ISBN: 978-3-540-77050-3
eBook Packages: Computer ScienceComputer Science (R0)