Abstract
We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T)=O(k⋅n 1/k)⋅w(MST(M)), and a spanning tree T′ with weight w(T′)=O(k)⋅w(MST(M)) and unweighted diameter O(k⋅n 1/k). These trees also achieve an optimal maximum degree. Furthermore, we demonstrate that these trees can be constructed efficiently.
We prove that these tradeoffs between unweighted diameter and weight are tight up to constant factors in the entire range of parameters. Moreover, our lower bounds apply to a basic one-dimensional Euclidean space.
Our lower bounds for the particular case of unweighted diameter O(log n) are of independent interest, settling a long-standing open problem in Computational Geometry. In STOC’95 Arya et al. devised a construction of Euclidean Spanners with unweighted diameter O(log n) and weight O(log n)⋅w(MST(M)). In SODA’05 Agarwal et al. showed that this result is tight up to a factor of O(log log n). We close this gap and show that the result of Arya et al. is tight up to constant factors.
Finally, our upper bounds imply improved approximation algorithms for the minimum h -hop spanning tree and bounded diameter minimum spanning tree problems for metric spaces.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abraham, I., Malkhi, D.: Compact routing on euclidian metrics. In: Proc. of 23rd Annual Symp. on Principles of Distributed Computing, pp. 141–149 (2004)
Agarwal, P.K., Wang, Y., Yin, P.: Lower bound for sparse Euclidean spanners. In: Proc. of 16th SODA, pp. 670–671 (2005)
Alon, N., Karp, R.M., Peleg, D., West, D.B.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24(1), 78–100 (1995)
Alpert, C.J., Hu, T.C., Huang, J.H., Kahng, A.B., Karger, D.: Prim–Dijkstra tradeoffs for improved performance-driven routing tree design. IEEE Trans. CAD Integr. Circuits Syst. 14(7), 890–896 (1995)
Althaus, E., Funke, S., Har-Peled, S., Könemann, J., Ramos, E.A., Skutella, M.: Approximating k-hop minimum-spanning trees. Oper. Res. Lett. 33(2), 115–120 (2005)
Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.H.M.: Euclidean spanners: short, thin, and lanky. In: Proc. of 27th STOC, pp. 489–498 (1995)
Arya, S., Mount, D.M., Smid, M.H.M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proc. of 35th FOCS, pp. 703–712 (1994)
Arya, S., Smid, M.H.M.: Efficient construction of a bounded degree spanner with low weight. Algorithmica 17(1), 33–54 (1997)
Awerbuch, B., Baratz, A., Peleg, D.: Cost-sensitive analysis of communication protocols. In: Proc. of 9th PODC, pp. 177–187 (1990)
Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and light-weight spanners. Manuscript (1991)
Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proc. of 37th FOCS, pp. 184–193 (1996)
Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proc. of 30th STOC, pp. 161–168 (1998)
Bharath-Kumar, K., Jaffe, J.M.: Routing to multiple destinations in computer networks. IEEE Trans. Commun. COM-31, 343–351 (1983)
Bose, P., Gudmundsson, J., Smid, M.H.M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42(3–4), 249–264 (2005)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields. In: Proc. of 24th STOC, pp. 546–556 (1992)
Chan, H.T.-H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. In: Proc. of 17th SODA, pp. 70–78 (2006)
Chan, T.M.: Well-separated pair decomposition in linear time? Inf. Process. Lett. 107(5), 138–141 (2008)
Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.A.: Approximating a finite metric by a small number of tree metrics. In: Proc. of 39th FOCS, pp. 379–388 (1998)
Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73–91 (1999)
Charikar, M., Hajiaghayi, M.T., Karloff, H.J., Rao, S.: \(l_{2}^{2}\) spreading metrics for vertex ordering problems. In: Proc. of 17th SODA, pp. 1018–1027 (2006)
Chazelle, B., Rosenberg, B.: The complexity of computing partial sums off-line. Int. J. Comput. Geom. Appl. 1, 33–45 (1991)
Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. In: Proc. of 34th FOCS, pp. 648–658 (1993)
Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. In: Proc. of 26th STOC, pp. 16–26 (1994)
Cong, J., Kahng, A.B., Robins, G., Sarrafzadeh, M., Wong, C.K.: Performance-driven global routing for cell based ics. In: Proc. of IEEE International Conference on Computer Design: VLSI in Computer & Processors (ICCD), pp. 170–173 (1991)
Cong, J., Kahng, A.B., Robins, G., Sarrafzadeh, M., Wong, C.K.: Provably good algorithms for performance-driven global routing. In: Proc. of IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2240–2243 (1992)
Cong, J., Kahng, A.B., Robins, G., Sarrafzadeh, M., Wong, C.K.: Provably good performance-driven global routing. IEEE Trans. CAD Integr. Circuits Syst. 11(6), 739–752 (1992)
Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, Boston (2001)
Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. In: Proc. of 10th SOCG, pp. 132–139 (1994)
Elkin, M., Emek, Y., Spielman, D., Teng, S.: Lower stretch spanning trees. In: Proc. of 37th STOC, pp. 494–503 (2005)
Eppstein, D.: Spanning trees and spanners. Technical report, Dept. of Information and Computer-Science, University of California, Irvine (96-16) (1996)
Even, G., Naor, J., Rao, S., Schieber, B.: Divide-and-conquer approximation algorithms via spreading metrics. In: Proc. of 36th FOCS, pp. 62–71 (1995)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proc. of 35th STOC, pp. 448–455 (2003)
Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1), 26–29 (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gouveia, L., Magnanti, T.L.: Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41(3), 159–173 (2003)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1994)
Hassin, Y., Peleg, D.: Sparse communication networks and efficient routing in the plane. In: Proc. of 19th PODC, pp. 41–50 (2000)
Jaffe, J.M.: Distributed multi-destination routing: the constraints of local information. SIAM J. Comput. 14, 875–888 (1985)
Kantor, E., Peleg, D.: Approximate hierarchical facility location and applications to the shallow Steiner tree and range assignment problems. In: Proc. of 6th CIAC, pp. 211–222 (2006)
Khuller, S., Raghavachari, B., Young, N.E.: Balancing minimum spanning and shortest path trees. In: Proc. of 4th SODA, pp. 243–250 (1993)
Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Appl. Math. 93(2–3), 265–285 (1999)
Laue, S., Matijevic, D.: Approximating k-hop minimum spanning trees in Euclidean metrics. In: Proc. of 19th CCCG, pp. 117–120 (2007)
Lenhof, H.P., Salowe, J.S., Wrege, D.E.: New methods to mix shortest-path and minimum spanning trees. Manuscript (1994)
Mansour, Y., Peleg, D.: An approximation algorithm for min-cost network design. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 53, 97–106 (2000)
Marathe, M.V., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Bicriteria network design problems. J. Algorithms 28(1), 142–171 (1998)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Pǎtraşcu, M., Demaine, E.D.: Tight bounds for the partial-sums problem. In: Proc. of 15th SODA, pp. 20–29 (2004)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Rao, S., Richa, A.W.: New approximation techniques for some ordering problems. In: Proc. of 9th SODA, pp. 211–218 (1998)
Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees short or small. In: Proc. of 5th SODA, pp. 546–555 (1994)
Yao, A.C.: Space-time tradeoff for answering range queries. In: Proc. of 14th STOC, pp. 128–136 (1982)
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by the Lynn and William Frankel Center for Computer Sciences.
Research of M. Elkin and S. Solomon has been supported by the Israeli Academy of Science, grant 483/06.
Rights and permissions
About this article
Cite this article
Dinitz, Y., Elkin, M. & Solomon, S. Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. Discrete Comput Geom 43, 736–783 (2010). https://doi.org/10.1007/s00454-009-9230-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9230-y