×

Light spanners for high dimensional norms via stochastic decompositions. (English) Zbl 1541.68391

Summary: Spanners for low dimensional spaces (e.g. Euclidean space of constant dimension, or doubling metrics) are well understood. This lies in contrast to the situation in high dimensional spaces, where except for the work of S. Har-Peled et al. [SODA 2013, 804–809 (2013; Zbl 1421.68176)], who showed that any \(n\)-point Euclidean metric has an \(O(t)\)-spanner with \(\tilde{O}(n^{1+1/t^2})\) edges, little is known. In this paper we study several aspects of spanners in high dimensional normed spaces. First, we build spanners for finite subsets of \(\ell_p\) with \(1<p\le 2\). Second, our construction yields a spanner which is both sparse and also light, i.e., its total weight is not much larger than that of the minimum spanning tree. In particular, we show that any \(n\)-point subset of \(\ell_p\) for \(1<p\le 2\) has an \(O(t)\)-spanner with \(n^{1+\tilde{O}(1/t^p)}\) edges and lightness \(n^{\tilde{O}(1/t^p)}\). In fact, our results are more general, and they apply to any metric space admitting a certain low diameter stochastic decomposition. It is known that arbitrary metric spaces have an \(O(t)\)-spanner with lightness \(O(n^{1/t})\). We exhibit the following tradeoff: metrics with decomposability parameter \(\nu =\nu (t)\) admit an \(O(t)\)-spanner with lightness \(\tilde{O}(\nu^{1/t})\). For example, metrics with doubling constant \(\lambda\), graphs of genus \(g\), and graphs of treewidth \(k\), all have spanners with stretch \(O(t)\) and lightness \(\tilde{O}(\lambda^{1/t})\), \(\tilde{O}(g^{1/t})\), \(\tilde{O}(k^{1/t})\) respectively. While these families do admit a \((1+\epsilon)\)-spanner, its lightness depend exponentially on the dimension (resp. \(\log g\), \(k)\). Our construction alleviates this exponential dependency, at the cost of incurring larger stretch.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
54E35 Metric spaces, metrizability
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1421.68176

References:

[1] Abraham, I.; Bartal, Y.; Neiman, O., Advances in metric embedding theory, Adv. Math., 228, 6, 3026-3126 (2011) · Zbl 1250.46016 · doi:10.1016/j.aim.2011.08.003
[2] Awerbuch, B., Baratz, A. E., Peleg, D.: Cost-sensitive analysis of communication protocols. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, Quebec City, Quebec, Canada, August 22-24, 1990, pp 177-187, (1990)
[3] Awerbuch, B., Baratz, A. E., Peleg, D.: Efficient broadcast and light-weight spanners. Manuscript, (1991)
[4] Ahmed, AR; Bodwin, G.; Sahneh, FD; Hamm, K.; Jebelli, MJL; Kobourov, SG; Spence, R., Graph spanners: A tutorial review, Comput. Sci. Rev., 37, 100253 (2020) · Zbl 1478.68206 · doi:10.1016/j.cosrev.2020.100253
[5] Abraham, I.; Chechik, S.; Elkin, M.; Filtser, A.; Neiman, O., Ramsey spanning trees and their applications, ACM Trans. Algorithms, 16, 2, 19:1-19:21 (2020) · Zbl 1484.68147 · doi:10.1145/3371039
[6] Althöfer, I.; Das, G.; Dobkin, DP; Joseph, D.; Soares, J., On sparse spanners of weighted graphs, Discrete Comput. Geom., 9, 81-100 (1993) · Zbl 0762.05039 · doi:10.1007/BF02189308
[7] Abraham, I.; Gavoille, C.; Gupta, A.; Neiman, O.; Talwar, K., Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs, SIAM J. Comput., 48, 3, 1120-1145 (2019) · Zbl 1432.05077 · doi:10.1137/17M1112406
[8] Ahn, K. J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In Michael Benedikt, Markus Krötzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pp 5-14. ACM, (2012)
[9] Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp 459-468, (2006)
[10] Awerbuch, B.: Communication-time trade-offs in network synchronization. In Proc. of 4th PODC, pp 272-276, (1985)
[11] Awerbuch, B., Complexity of network synchronization, J. ACM, 32, 4, 804-823 (1985) · Zbl 0628.68045 · doi:10.1145/4221.4227
[12] Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In Proc. of 37th FOCS, pp 184-193, (1996)
[13] Biswas, A. S., Dory, M., Ghaffari, M., Mitrovic, S., Nazari, Y.: Massively parallel algorithms for distance approximation and spanners. In Kunal Agrawal and Yossi Azar, editors, SPAA ’21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pp 118-128. ACM, (2021)
[14] Bhore, S., Filtser, A., Khodabandeh, H., Tóth, C. D.: Online spanners in metric spaces. CoRR, arXiv:2202.09991, (2022)
[15] Braynard, R., Kostic, D., Rodriguez, A., Chase, J., Vahdat, A.: Opus: an overlay peer utility service. In Prof. of 5th OPENARCH, (2002)
[16] Biswal, P.; Lee, JR; Rao, S., Eigenvalue bounds, spectral partitioning, and metrical deformations via flows, J. ACM, 57, 3, 1-23 (2010) · Zbl 1327.05199 · doi:10.1145/1706591.1706593
[17] Borradaile, G., Le, H., Wulff-Nilsen, C.: Minor-free graphs have light spanners. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 767-778, (2017)
[18] Borradaile, G., Le, H., Wulff-Nilsen, C.: Greedy spanners are optimal in doubling metrics. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp 2371-2379. SIAM, (2019) · Zbl 1432.68340
[19] Chandra, B.; Das, G.; Narasimhan, G.; Soares, J., New sparseness results on graph spanners, Int. J. Comput. Geometry Appl., 5, 125-144 (1995) · Zbl 0818.68078 · doi:10.1142/S0218195995000088
[20] Coppersmith, D.; Elkin, M., Sparse sourcewise and pairwise distance preservers, SIAM J. Discrete Math., 20, 2, 463-501 (2006) · Zbl 1118.05025 · doi:10.1137/050630696
[21] Cohen-Addad, V., Filtser, A., Klein, P. N., Le, H.: On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp 589-600. IEEE, (2020)
[22] 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, pages 546-556, (1992)
[23] Calinescu, G.; Karloff, H.; Rabani, Y., Approximation algorithms for the 0-extension problem, SIAM J. Comput., 34, 2, 358-372 (2005) · Zbl 1087.68128 · doi:10.1137/S0097539701395978
[24] Cohen, E., Fast algorithms for constructing t-spanners and paths with stretch t, SIAM J. Comput., 28, 1, 210-236 (1998) · Zbl 0915.68077 · doi:10.1137/S0097539794261295
[25] Chechik, S.; Wulff-Nilsen, C., Near-optimal light spanners, ACM Trans. Algorithms, 14, 3, 33:1-33:15 (2018) · Zbl 1457.05029 · doi:10.1145/3199607
[26] Das, G., Heffernan, P. J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional euclidean space. In Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, CA, USA, May 19-21, 1993, pages 53-62, (1993)
[27] Kostic, D., Vahdat, A.: Latency versus cost optimizations in hierarchical overlay networks. Technical report, Duke University, (CS-2001-04), (2002)
[28] Elkin, M., Filtser, A., Neiman, O.: Distributed construction of light networks. In Yuval Emek and Christian Cachin, editors, PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pp 483-492. ACM, (2020) · Zbl 07323225
[29] Elkin, M., Computing almost shortest paths, ACM Trans. Algorithms, 1, 2, 283-323 (2005) · Zbl 1321.05258 · doi:10.1145/1103963.1103968
[30] Elkin, M., Neiman, O., Solomon, S.: Light spanners. In Proc. of 41th ICALP, pp 442-452, (2014) · Zbl 1412.05087
[31] Elkin, M.; Zhang, J., Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models, Distributed Computing, 18, 5, 375-385 (2006) · Zbl 1266.68212 · doi:10.1007/s00446-005-0147-2
[32] Filtser, A.: On strong diameter padded decompositions. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs, pages 6:1-6:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2019)
[33] Filtser, A.: Hop-constrained metric embeddings and their applications. In 62st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, February 7-10, 2022, pages 492-503. IEEE, (2021)
[34] Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In Proc. of 16th SODA, pp 745-754, (2005) · Zbl 1297.05073
[35] Filtser, A., Kapralov, M., Nouri, N.: Graph spanners by sketching in dynamic streams and the simultaneous communication model. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 1894-1913. SIAM, (2021) · Zbl 07788451
[36] Filtser, A., Le, H.: Clan embeddings into trees, and low treewidth graphs. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 342-355. ACM, (2021) · Zbl 07765176
[37] Filtser, A., Neiman, O.: Light spanners for high dimensional norms via stochastic decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 29:1-29:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2018) · Zbl 1524.68407
[38] Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, STOC ’03, pages 448-455, New York, NY, USA, (2003). ACM · Zbl 1192.68977
[39] Feige, U.; Schechtman, G., On the optimality of the random hyperplane rounding technique for max cut, Random Struct. Algorithms, 20, 3, 403-440 (2002) · Zbl 1005.90052 · doi:10.1002/rsa.10036
[40] Filtser, A., Solomon, S.: The greedy spanner is existentially optimal. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pp. 9-17, (2016) · Zbl 1376.68108
[41] Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of 44th FOCS, pages 534-543, (2003)
[42] Gottlieb, L.A.: A light metric spanner. In: Proceedings of 56th FOCS, pp 759-772, (2015)
[43] Grigni, M.: Approximate TSP in graphs with forbidden minors. In: Proceedings of 27th ICALP, pp 869-877, (2000) · Zbl 0973.68263
[44] Gross, JL; Tucker, TW, Topological Graph Theory (1987), New York, NY, USA: Wiley-Interscience, New York, NY, USA · Zbl 0621.05013
[45] Har-Peled, S., Indyk, P., Sidiropoulos, A.: Euclidean spanners in high dimensions. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp 804-809, (2013) · Zbl 1421.68176
[46] Har-Peled, S.; Mendel, M., Fast construction of nets in low-dimensional metrics and their applications, SIAM J. Comput., 35, 5, 1148-1184 (2006) · Zbl 1100.68014 · doi:10.1137/S0097539704446281
[47] Klein, P. N.: A subset spanner for planar graphs, : with application to subset TSP. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 749-756. ACM, (2006) · Zbl 1301.05335
[48] Krauthgamer, R., Lee, J. R., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp 434-443, Washington, DC, USA, (2004). IEEE Computer Society · Zbl 1108.46010
[49] Kelner, J. A., Lee, J. R., Price, G. N., Teng, S.-H.: Higher eigenvalues of graphs. In FOCS, pp 735-744, (2009) · Zbl 1292.05172
[50] Klein, P. N., Plotkin, S. A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In STOC, pp 682-690, (1993) · Zbl 1310.90017
[51] Linial, N.; London, E.; Rabinovich, Y., The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245 (1995) · Zbl 0827.05021 · doi:10.1007/BF01200757
[52] Lee, JR; Naor, A., Extending lipschitz functions via random metric partitions, Invent. Math., 160, 1, 59-95 (2005) · Zbl 1074.46004 · doi:10.1007/s00222-004-0400-5
[53] Leighton, T.; Rao, S., Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, 46, 787-832 (1999) · Zbl 1065.68666 · doi:10.1145/331524.331526
[54] Linial, N.; Saks, M., Low diameter graph decompositions, Combinatorica, 13, 4, 441-454 (1993) · Zbl 0790.05067 · doi:10.1007/BF01303516
[55] Lee, J. R., Sidiropoulos, A.: Genus and the geometry of the cut graph. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp 193-201, (2010) · Zbl 1288.05062
[56] Le, H., Solomon, S.: Truly optimal euclidean spanners. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1078-1100. IEEE Computer Society, (2019) · Zbl 07510280
[57] Mendel, M.; Naor, A., Ramsey partitions and proximity data structures, J. Eur. Math. Soc., 9, 2, 253-275 (2007) · Zbl 1122.68043 · doi:10.4171/JEMS/79
[58] Nguyen, H.L.: Approximate nearest neighbor search in \(\ell_p\). CoRR, arXiv:1306.3601, (2013)
[59] Narasimhan, G., Smid, Michiel H.M.: Geometric spanner networks. Cambridge University Press, (2007) · Zbl 1140.68068
[60] Peleg, D.: Proximity-preserving labeling schemes and their applications. In Graph-Theoretic Concepts in Computer Science, 25th International Workshop, WG ’99, Ascona, Switzerland, June 17-19, 1999, Proceedings, pp 30-41, (1999) · Zbl 0945.05053
[61] Peleg, D., Distributed Computing: A Locality-Sensitive Approach (2000), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 0959.68042 · doi:10.1137/1.9780898719772
[62] Parter, M., Rubinfeld, R., Vakilian, A., Yodpinyanee, A.: Local computation algorithms for spanners. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pp 58:1-58:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2019) · Zbl 07559101
[63] Peleg, D.; Ullman, JD, An optimal synchronizer for the hypercube, SIAM J. Comput., 18, 4, 740-747 (1989) · Zbl 0681.68091 · doi:10.1137/0218050
[64] Peleg, D.; Upfal, E., A trade-off between space and efficiency for routing tables, J. ACM, 36, 3, 510-530 (1989) · Zbl 0900.68262 · doi:10.1145/65950.65953
[65] Rao, S.B.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In SOCG, pp 300-306, (1999)
[66] Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, pp 261-272, (2005) · Zbl 1082.68087
[67] Roditty, L., Zwick, U.: On dynamic shortest paths problems. In Proc. of 32nd ESA, pp 580-591, (2004) · Zbl 1111.68599
[68] Salowe, J.S.: Construction of multidimensional spanner graphs, with applications to minimum spanning trees. In: Proceedings of 7th SoCG, pp 256-261, (1991)
[69] Smid, Michiel H.M.: The weak gap property in metric spaces of bounded doubling dimension. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pp 275-289, (2009) · Zbl 1257.05053
[70] Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp 281-290, (2004) · Zbl 1192.68918
[71] Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of 13th SPAA, pp 1-10, (2001)
[72] Thorup, M.; Zwick, U., Approximate distance oracles, J. ACM, 52, 1, 1-24 (2005) · Zbl 1175.68303 · doi:10.1145/1044731.1044732
[73] Vaidya, PM, A sparse graph almost as good as the complete graph on points in \(k\) dimensions, Discrete Comput. Geom., 6, 369-381 (1991) · Zbl 0755.05059 · doi:10.1007/BF02574695
[74] Vogel, J., Widmer, J., Farin, D., Mauve, M., Effelsberg, W.: Priority-based distribution trees for application-level multicast. In Proceedings of the 2nd Workshop on Network and System Support for Games, NETGAMES 2003, Redwood City, California, USA, May 22-23, 2003, pp 148-157, (2003)
[75] Wu, BY; Chao, K-M; Tang, CY, Light graphs with small routing cost, Networks, 39, 3, 130-138 (2002) · Zbl 1028.90075 · doi:10.1002/net.10019
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.