Low-light trees, and tight lower bounds for Euclidean spanners. (English) Zbl 1219.05184
Summary: 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\cdot n ^{1/k })\cdot w(MST(M))\), and a spanning tree \(T^{\prime}\) with weight \(w(T^{\prime})=O(k)\cdot w(MST(M))\) and unweighted diameter \(O(k\cdot 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. Arya et al. [S. Arya, G. Das, D.M. Mount, J.S. Salowe, and M. Smid, “Euclidean spanners: Short, thin, and lanky,” Proceedings of the 27th annual ACM symposium on the theory of computing (STOC). Las Vegas, NV, USA, May 29 - June 1, 1995. New York, NY: ACM, 489-498 (1995; Zbl 0968.68533)] devised a construction of Euclidean Spanners with unweighted diameter \(O(\log n)\) and weight \(O(\log n)\cdot w(MST(M))\).
P. K. Agarwal, Y. Wang and P. Yin [Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 670–671, ACM, New York (2005)] 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.
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. Arya et al. [S. Arya, G. Das, D.M. Mount, J.S. Salowe, and M. Smid, “Euclidean spanners: Short, thin, and lanky,” Proceedings of the 27th annual ACM symposium on the theory of computing (STOC). Las Vegas, NV, USA, May 29 - June 1, 1995. New York, NY: ACM, 489-498 (1995; Zbl 0968.68533)] devised a construction of Euclidean Spanners with unweighted diameter \(O(\log n)\) and weight \(O(\log n)\cdot w(MST(M))\).
P. K. Agarwal, Y. Wang and P. Yin [Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 670–671, ACM, New York (2005)] 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.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 54E35 | Metric spaces, metrizability |
| 68W25 | Approximation algorithms |
Keywords:
approximation algorithms; computational geometry; Euclidean spanners; hop-diameter; low distortion embeddingsCitations:
Zbl 0968.68533References:
| [1] | Abraham, I., Malkhi, D.: Compact routing on euclidian metrics. In: Proc. of 23rd Annual Symp. on Principles of Distributed Computing, pp. 141-149 (2004) · Zbl 1321.68015 |
| [2] | Agarwal, P.K., Wang, Y., Yin, P.: Lower bound for sparse Euclidean spanners. In: Proc. of 16th SODA, pp. 670-671 (2005) · Zbl 1297.05065 |
| [3] | 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) · Zbl 0818.90147 · doi:10.1137/S0097539792224474 |
| [4] | 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) · doi:10.1109/43.391737 |
| [5] | 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) · Zbl 1099.90064 · doi:10.1016/j.orl.2004.05.005 |
| [6] | 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) · Zbl 0968.68533 |
| [7] | 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) |
| [8] | Arya, S., Smid, M.H.M.: Efficient construction of a bounded degree spanner with low weight. Algorithmica 17(1), 33-54 (1997) · Zbl 0864.68108 · doi:10.1007/BF02523237 |
| [9] | Awerbuch, B., Baratz, A., Peleg, D.: Cost-sensitive analysis of communication protocols. In: Proc. of 9th PODC, pp. 177-187 (1990) |
| [10] | Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and light-weight spanners. Manuscript (1991) |
| [11] | Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proc. of 37th FOCS, pp. 184-193 (1996) |
| [12] | Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proc. of 30th STOC, pp. 161-168 (1998) · Zbl 1029.68951 |
| [13] | Bharath-Kumar, K., Jaffe, J.M.: Routing to multiple destinations in computer networks. IEEE Trans. Commun. COM-31, 343-351 (1983) · Zbl 0505.68031 · doi:10.1109/TCOM.1983.1095818 |
| [14] | Bose, P., Gudmundsson, J., Smid, M.H.M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42(3-4), 249-264 (2005) · Zbl 1086.68136 · doi:10.1007/s00453-005-1168-8 |
| [15] | 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) |
| [16] | Chan, H.T.-H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. In: Proc. of 17th SODA, pp. 70-78 (2006) · Zbl 1192.05037 |
| [17] | Chan, T.M.: Well-separated pair decomposition in linear time? Inf. Process. Lett. 107(5), 138-141 (2008) · Zbl 1186.68492 · doi:10.1016/j.ipl.2008.02.008 |
| [18] | 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) |
| [19] | 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) · Zbl 0937.68155 · doi:10.1006/jagm.1999.1042 |
| [20] | 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) · Zbl 1192.68875 |
| [21] | Chazelle, B., Rosenberg, B.: The complexity of computing partial sums off-line. Int. J. Comput. Geom. Appl. 1, 33-45 (1991) · Zbl 0724.68047 · doi:10.1142/S0218195991000049 |
| [22] | Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. In: Proc. of 34th FOCS, pp. 648-658 (1993) |
| [23] | Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. In: Proc. of 26th STOC, pp. 16-26 (1994) · Zbl 1344.68283 |
| [24] | 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) |
| [25] | 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) |
| [26] | 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) · doi:10.1109/43.137519 |
| [27] | Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, Boston (2001) · Zbl 1047.68161 |
| [28] | Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. In: Proc. of 10th SOCG, pp. 132-139 (1994) |
| [29] | Elkin, M., Emek, Y., Spielman, D., Teng, S.: Lower stretch spanning trees. In: Proc. of 37th STOC, pp. 494-503 (2005) · Zbl 1192.05028 |
| [30] | Eppstein, D.: Spanning trees and spanners. Technical report, Dept. of Information and Computer-Science, University of California, Irvine (96-16) (1996) |
| [31] | 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) · Zbl 0938.68916 |
| [32] | 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) · Zbl 1192.68977 |
| [33] | Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1), 26-29 (2007) · Zbl 1185.68856 · doi:10.1016/j.ipl.2006.07.009 |
| [34] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979) · Zbl 0411.68039 |
| [35] | Gouveia, L., Magnanti, T.L.: Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41(3), 159-173 (2003) · Zbl 1106.90014 · doi:10.1002/net.10069 |
| [36] | Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1994) · Zbl 0836.00001 |
| [37] | Hassin, Y., Peleg, D.: Sparse communication networks and efficient routing in the plane. In: Proc. of 19th PODC, pp. 41-50 (2000) · Zbl 1314.68025 |
| [38] | Jaffe, J.M.: Distributed multi-destination routing: the constraints of local information. SIAM J. Comput. 14, 875-888 (1985) · Zbl 0575.68070 · doi:10.1137/0214062 |
| [39] | 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) · Zbl 1183.90279 |
| [40] | Khuller, S., Raghavachari, B., Young, N.E.: Balancing minimum spanning and shortest path trees. In: Proc. of 4th SODA, pp. 243-250 (1993) · Zbl 0801.68134 |
| [41] | Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Appl. Math. 93(2-3), 265-285 (1999) · Zbl 0931.68077 · doi:10.1016/S0166-218X(99)00111-0 |
| [42] | Laue, S., Matijevic, D.: Approximating k-hop minimum spanning trees in Euclidean metrics. In: Proc. of 19th CCCG, pp. 117-120 (2007) · Zbl 1186.68562 |
| [43] | Lenhof, H.P., Salowe, J.S., Wrege, D.E.: New methods to mix shortest-path and minimum spanning trees. Manuscript (1994) |
| [44] | Mansour, Y., Peleg, D.: An approximation algorithm for min-cost network design. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 53, 97-106 (2000) · Zbl 0963.68231 |
| [45] | 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) · Zbl 0906.68076 · doi:10.1006/jagm.1998.0930 |
| [46] | Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007) · Zbl 1140.68068 · doi:10.1017/CBO9780511546884 |
| [47] | Pǎtraşcu, M., Demaine, E.D.: Tight bounds for the partial-sums problem. In: Proc. of 15th SODA, pp. 20-29 (2004) · Zbl 1317.68080 |
| [48] | Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000) · Zbl 0959.68042 |
| [49] | Rao, S., Richa, A.W.: New approximation techniques for some ordering problems. In: Proc. of 9th SODA, pp. 211-218 (1998) · Zbl 0930.68108 |
| [50] | 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) · Zbl 0867.90120 |
| [51] | Yao, A.C.: Space-time tradeoff for answering range queries. In: Proc. of 14th STOC, pp. 128-136 (1982) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
