Document Open Access Logo

Terminal Embeddings

Authors Michael Elkin, Arnold Filtser, Ofer Neiman

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.242.pdf
  • Filesize: 0.62 MB
  • 23 pages

Document Identifiers

Author Details

Michael Elkin
Arnold Filtser
Ofer Neiman

Cite As Get BibTex

Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 242-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.242

Abstract

In this paper we study terminal embeddings, in which one is given a finite metric (X,d_X) (or a graph G=(V,E)) and a subset K of X of its points are designated as terminals. The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve approx |K| * |X| pairs, the distortion depends only on |K|, rather than on |X|.

We also strengthen this notion, and consider embeddings that approximately preserve the distances between all pairs, but provide improved distortion  for pairs containing a terminal. Surprisingly, we show that such embeddings exist  in many settings, and have optimal distortion bounds both with respect to X \times  X and with respect to K * X.

Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, Arora et. al. devised an ~O(sqrt(log(r))-approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an ~O(sqrt(log |K|)-approximation for sparsest-cut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since |K| <= r, our bound generalizes that of Arora et al.

Subject Classification

Keywords
  • embedding
  • distortion
  • terminals

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, Yair Bartal, and Ofer Neiman. Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. In SODA, pages 502-511, 2007. Google Scholar
  2. Ittai Abraham, Yair Bartal, and Ofer Neiman. Advances in metric embedding theory. Advances in Mathematics, 228(6):3026-3126, 2011. Google Scholar
  3. Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In STOC, pages 395-406, 2012. Google Scholar
  4. Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78-100, 1995. Google Scholar
  5. I. Altḧofer, G. Das, D. P. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. Google Scholar
  6. Reid Andersen and Uriel Feige. Interchanging distance and capacity in probabilistic mappings, 2009. Google Scholar
  7. S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society 21, 1:1-21, 2008. Google Scholar
  8. Sanjeev Arora, James R. Lee, and Assaf Naor. Fréchet embeddings of negative type metrics. Discrete & Computational Geometry, 38(4):726-739, 2007. Google Scholar
  9. Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2), 2009. Google Scholar
  10. Yonatan Aumann and Yuval Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291-301, 1998. Google Scholar
  11. B. Awerbuch, A. Baratz, and D. Peleg. Efficient broadcast and light-weight spanners. Technical Report CS92-22, The Weizmann Institute of Science, Rehovot, Israel., 1992. Google Scholar
  12. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In FOCS, pages 184-193, 1996. Google Scholar
  13. Yair Bartal, Amos Fiat, and Yuval Rabani. Competitive algorithms for distributed data management. J. Comput. Syst. Sci., 51(3):341-358, 1995. Google Scholar
  14. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. Some low distortion metric ramsey problems. Discrete & Computational Geometry, 33(1):27-41, 2005. Google Scholar
  15. J. Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):46-52, 1985. Google Scholar
  16. T.-H. Chan, Donglin Xia, Goran Konjevod, and Andrea Richa. A tight lower bound for the steiner point removal problem on trees. In Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation, APPROX'06/RANDOM'06, pages 70-81, Berlin, Heidelberg, 2006. Springer-Verlag. Google Scholar
  17. Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra. Vertex sparsifiers and abstract rounding algorithms. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 265-274, 2010. Google Scholar
  18. Don Coppersmith and Michael Elkin. Sparse source-wise and pair-wise distance preservers. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'05, pages 660-669, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. Google Scholar
  19. Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. SIAM Journal on Computing, 38(2):608-628, 2008. Google Scholar
  20. Michael Elkin, Arnold Filtser, and Ofer Neiman. Prioritized metric structures and embedding. In Proceedings of the 47th ACM Symposium on Theory of Computing, STOC'15, 2015. Google Scholar
  21. Michael Elkin and Shay Solomon. Steiner shallow-light trees are exponentially lighter than spanning ones. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 373-382, 2011. Google Scholar
  22. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar. Vertex sparsifiers: New results from old techniques. SIAM J. Comput., 43(4):1239-1262, 2014. Google Scholar
  23. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. Google Scholar
  24. T. Figiel, J. Lindenstrauss, and V.D. Milman. The dimension of almost spherical sections of convex bodies. Acta Mathematica, 139(1):53-94, 1977. Google Scholar
  25. E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, Jan 1968. Google Scholar
  26. Anupam Gupta. Steiner points in tree metrics don't (really) help. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'01, pages 220-227, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. Google Scholar
  27. Anupam Gupta, Viswanath Nagarajan, and R. Ravi. An improved approximation algorithm for requirement cut. Oper. Res. Lett., 38(4):322-325, 2010. Google Scholar
  28. Sariel Har-Peled, Piotr Indyk, and Anastasios Sidiropoulos. Euclidean spanners in high dimensions. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'13, pages 804-809. SIAM, 2013. Google Scholar
  29. William Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189–206, 1984. Google Scholar
  30. Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen. Cutting corners cheaply, or how to remove steiner points. In SODA, pages 1029-1040, 2014. Google Scholar
  31. Telikepalli Kavitha and Nithin M. Varma. Small stretch pairwise spanners. In Proceedings of the 40th International Conference on Automata, Languages, and Programming - Volume Part I, ICALP'13, pages 601-612, Berlin, Heidelberg, 2013. Springer-Verlag. Google Scholar
  32. Samir Khuller, Balaji Raghavachari, and Neal E. Young. Balancing minimum spanning trees and shortest-path trees. Algorithmica, 14(4):305-321, 1995. Google Scholar
  33. Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor. Measured descent: a new embedding method for finite metrics. Geometric and Functional Analysis, 15(4):839-858, 2005. Google Scholar
  34. Frank Thomson Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999. Google Scholar
  35. N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  36. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. In FOCS, pages 109-118, 2006. Google Scholar
  37. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In FOCS, pages 3-12, 2009. Google Scholar
  38. Yuri Rabinovich and Ran Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete & Computational Geometry, 19(1):79-94, 1998. Google Scholar
  39. Harald Räcke. Minimizing congestion in general networks. In Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS'02, pages 43-52, Washington, DC, USA, 2002. IEEE Computer Society. Google Scholar
  40. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In STOC, pages 255-264, 2008. Google Scholar
  41. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proceedings of the 32Nd International Conference on Automata, Languages and Programming, ICALP'05, pages 261-272, Berlin, Heidelberg, 2005. Springer-Verlag. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact