Article

Bypassing the embedding: algorithms for low dimensional metrics

Author:

Kunal TalwarAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 281 - 290

https://doi.org/10.1145/1007352.1007399

Published: 13 June 2004 Publication History

Abstract

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2^k balls of radius r. This concept for abstract metrics has been proposed as a natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics:

Quasi-polynomial time (1+ε)-approximation algorithm for various optimization problems such as TSP, k-median and facility location.

(1+ε)-approximate distance labeling scheme with optimal label length.

(1+ε)-stretch polylogarithmic storage routing scheme.

References

[1]

N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78--100, 1995.]]

Digital Library

[2]

S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In 37th Annual Symposium on Foundations of Computer Science, pages 2--11, Burlington, Vermont, 14--16 Oct. 1996. IEEE.]]

Digital Library

[3]

S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753--782, 1998.]]

Digital Library

[4]

S. Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Mathematical Programming, 97(1--2):43--69, 2003.]]

[5]

S. Arora, P. Raghavan, and S. Rao. Approximation schemes for Euclidean k-medians and related problems. In ACM Symposium on Theory of Computing (STOC), 1998.]]

Digital Library

[6]

P. Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4):429--448, 1983.]]

[7]

B. Awerbuch, A. B. Noy, N. Linial, and D. Peleg. Improved routing strategies with succinct tables. J. Algorithms, 11(3):307--341, 1990.]]

Digital Library

[8]

B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discret. Math., 5(2):151--162, 1992.]]

Digital Library

[9]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, pages 184--193. IEEE, 1996.]]

Digital Library

[10]

Y. Bartal. On approximating arbitrary metrices by tree metrics. In 30th Annual ACM Symposium on Theory of Computing, pages 161--168. ACM, 1998.]]

Digital Library

[11]

A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher. Min-wise independent permutations. Journal of Computer and System Sciences, 60(3):630--659, 2000.]]

Digital Library

[12]

G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. In 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 8--16. SIAM, 2001.]]

Digital Library

[13]

P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67--90, 1995.]]

Digital Library

[14]

M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, page 379. IEEE Computer Society, 1998.]]

Digital Library

[15]

K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom., 22(1):63--93, 1999.]]

[16]

L. J. Cowen. Compact routing with minimum stretch. J. Algorithms, 38(1):170--183, 2001.]]

Digital Library

[17]

T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor (extended abstract). In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 11--20. ACM Press, 1998.]]

Digital Library

[18]

J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar. An improved approximation algorithm for the 0-extension problem. In ACM-SIAM Symposium on Discrete Algorithms. 2003.]]

Digital Library

[19]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In 35th Annual ACM Symposium on Theory of Computing. ACM, 2003.]]

Digital Library

[20]

C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg. Approximate distance labeling schemes. In Proceedings of the 9th Annual European Symposium on Algorithms, pages 476--487. Springer-Verlag, 2001.]]

Digital Library

[21]

C. Gavoille and D. Peleg. Compact and localized distributed data structures. Distrib. Comput., 16(2-3):111--120, 2003.]]

Digital Library

[22]

C. Gavoille, D. Peleg, S. Perennes, and R. Raz. Distance labeling in graphs. In ACM-SIAM Symposium on Discrete Algorithms, pages 210--219, 2001.]]

Digital Library

[23]

J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. Smid. Approximate distance oracles for geometric graphs. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 828--837. Society for Industrial and Applied Mathematics, 2002.]]

Digital Library

[24]

A. Gupta, R. Krauthgamer, and J. Lee. Bounded geometries, fractals and low-distortion embeddings. In Foundations of Computer Science, 2003.]]

Digital Library

[25]

S. Har-Peled and S. Mazumdar. Coresets for k-means and $k$-median clustering and their applications. In These Proceedings, 2004.]]

Digital Library

[26]

K. Hildrum, J. Kubiatowicz, S. Ma, and S. Rao. A note on finding the nearest neighbor in growth-restricted metrics. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 553--4, 2004.]]

Digital Library

[27]

P. Indyk. Algorithms for dynamic geometric problems over data streams. In These Proceedings, 2004.]]

Digital Library

[28]

D. Karger and M. Ruhl. Finding nearest neighbors in growth-restricted metrics. In 34th Annual ACM Symposium on the Theory of Computing, pages 63--66, 2002.]]

Digital Library

[29]

S. Kolliopoulos and S. Rao. A nearly linear-time approximation scheme for the Euclidean k-median problem. In ESA: Annual European Symposium on Algorithms, 1999.]]

Digital Library

[30]

R. Krauthgamer and J. Lee. Navigating nets: simple algirithms for proximity search. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004.]]

Digital Library

[31]

R. Krauthgamer and J. Lee. Nearest neighbour search in the blackbox model. Manuscript, 2004.]]

[32]

T. J. Laakso. Plane with A∞-weighted metric not bi-Lipschitz embeddable to RN. Bull. London Math. Soc., 34(6):667--676, 2002.]]

[33]

U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285--307, 2001.]]

[34]

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.]]

[35]

J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4):1298--1309, Aug. 1999.]]

Digital Library

[36]

T. S. E. Ng and H. Zhang. Predicting internet network distance with coordinates-based approaches. In 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM-02), pages 170--179, 2002.]]

[37]

D. Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, 2000.]]

Digital Library

[38]

D. Peleg. Proximity preserving labeling schemes. Journal of Graph Theory, 33:167--176, 2000.]]

Digital Library

[39]

D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510--530, 1989.]]

Digital Library

[40]

S. A. Plotkin, D. B. Shmoys, and Eva Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20(2):257--301, 1995.]]

[41]

S. B. Rao and W. D. Smith. Approximating geometrical graphs via spanners and banyans. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 540--550. ACM Press, 1998.]]

Digital Library

[42]

J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.]]

[43]

M. Thorup and U. Zwick. Approximate distance oracles. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 183--192. ACM Press, 2001.]]

Digital Library

[44]

M. Thorup and U. Zwick. Compact routing schemes. In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 1--10. ACM Press, 2001.]]

Digital Library

[45]

L. Trevisan. When Hamming meets Euclid: The approximability of geometric TSP and steiner tree. SICOMP: SIAM Journal on Computing, 30, 2000.]]

Digital Library

Cited By

Mo GSong SDing H(2024)Towards Metric DBSCAN: Exact, Approximate, and Streaming AlgorithmsProceedings of the ACM on Management of Data10.1145/36549812:3(1-25)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654981
Bose PTuttle T(2024)Routing on heavy path WSPD spannersComputational Geometry: Theory and Applications10.1016/j.comgeo.2024.102121123:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2024.102121
Charikar MHenzinger MHu LVötsch MWaingarten EOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Simple, scalable and effective clustering via one-dimensional projectionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668942(64618-64649)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668942
Show More Cited By

Index Terms

Bypassing the embedding: algorithms for low dimensional metrics
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
  2. Randomness, geometry and discrete structures

Recommendations

Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

Spanners for metric spaces have been extensively studied, perhaps most notably in low-dimensional Euclidean spaces - due to their numerous applications. Euclidean spanners can be viewed as means of compressing the (n2) pairwise distances of a d-...
On Hierarchical Routing in Doubling Metrics

We study the problem of routing in doubling metrics and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a metric (...
Balancing Degree, Diameter, and Weight in Euclidean Spanners

In a seminal paper from 1995, Arya et al. [Euclidean spanners: Short, thin, and lanky, in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM, New York, 1995, pp. 489--498] devised a construction that, for any set $S$ of $n$ points in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

163
Total Citations
View Citations
1,070
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)7

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mo GSong SDing H(2024)Towards Metric DBSCAN: Exact, Approximate, and Streaming AlgorithmsProceedings of the ACM on Management of Data10.1145/36549812:3(1-25)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654981
Bose PTuttle T(2024)Routing on heavy path WSPD spannersComputational Geometry: Theory and Applications10.1016/j.comgeo.2024.102121123:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2024.102121
Charikar MHenzinger MHu LVötsch MWaingarten EOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Simple, scalable and effective clustering via one-dimensional projectionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668942(64618-64649)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668942
Ding HLiu WYe M(2023)A Data-dependent Approach for High-dimensional (Robust) Wasserstein AlignmentACM Journal of Experimental Algorithmics10.1145/360491028(1-32)Online publication date: 11-Aug-2023
https://dl.acm.org/doi/10.1145/3604910
Jayaprakash ASalavatipour M(2023)Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway DimensionACM Transactions on Algorithms10.1145/358250019:2(1-36)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1145/3582500
Chang HConroy JLe HMilenkovic LSolomon SThan C(2023)Covering Planar Metrics (and Beyond): O(1) Trees Suffice2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00139(2231-2261)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00139
Wu DFeng QWang J(2023)Approximation Algorithms for Fair k-median Problem without Fairness ViolationTheoretical Computer Science10.1016/j.tcs.2023.114332(114332)Online publication date: Dec-2023
https://doi.org/10.1016/j.tcs.2023.114332
Wu DXu JWang J(2023)A PTAS Framework for Clustering Problems in Doubling MetricsComputing and Combinatorics10.1007/978-3-031-49190-0_28(384-397)Online publication date: 9-Dec-2023
https://doi.org/10.1007/978-3-031-49190-0_28
Cohen-Addad VLeonardi SGupta A(2022)Bypassing the surface embedding: approximation schemes for network design in minor-free graphsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520049(343-356)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520049
Filtser ALe H(2022)Low Treewidth Embeddings of Planar and Minor-Free Metrics2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00105(1081-1092)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00105
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents