The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Probabilistic approximation of metric spaces and its algorithmic applications
Abstract
This paper provides a novel technique for the analysis of randomized algorithms for optimization problems on metric spaces, by relating the randomized performance ratio for any, metric space to the randomized performance ratio for a set of "simple" metric spaces. We define a notion of a set of metric spaces that probabilistically-approximates another metric space. We prove that any metric space can be probabilistically-approximated by hierarchically well-separated trees (HST) with a polylogarithmic distortion. These metric spaces are "simple" as being: (1) tree metrics; (2) natural for applying a divide-and-conquer algorithmic approach. The technique presented is of particular interest in the context of on-line computation. A large number of on-line algorithmic problems, including metrical task systems, server problems, distributed paging, and dynamic storage rearrangement are defined in terms of some metric space. Typically for these problems, there are linear lower bounds on the competitive ratio of deterministic algorithms. Although randomization against an oblivious adversary has the potential of overcoming these high ratios, very little progress has been made in the analysis. We demonstrate the use of our technique by obtaining substantially improved results for two different on-line problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B. (1984) · Medical Entomology and Zoology · Cited by 661
On lipschitz embedding of finite metric spaces in Hilbert space
Bourgain, J. (1985) · Israel Journal of Mathematics · doi:10.1007/bf02776078 · Cited by 560
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457
An optimal on-line algorithm for metrical task system
Borodin, A., Linial, N., & Saks, M. E. (1992) · Journal of the ACM · doi:10.1145/146585.146588 · Cited by 326
A Graph-Theoretic Game and Its Application to the k -Server Problem
Alon, N., Karp, R. M., Peleg, D., & West, D. B. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792224474 · Cited by 303
On the power of randomization in on-line algorithms
Ben-David, S., Borodin, A., Karp, R., Tardos, G., & Wigderson, A. (1994) · Algorithmica · doi:10.1007/bf01294260 · Cited by 262
New Ressults on Server Problems
Chrobak, M., Karloof, H., Payne, T., & Vishwnathan, S. (1991) · SIAM Journal on Discrete Mathematics · doi:10.1137/0404017 · Cited by 208
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 190
On the power of randomization in online algorithms
Ben-David, S., Borodin, A., Karp, R., Tardos, G., & Wigderson, A. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100268 · Cited by 174
An Optimal On-Line Algorithm for K Servers on Trees
Chrobák, M., & Larmore, L. L. (1991) · SIAM Journal on Computing · doi:10.1137/0220008 · Cited by 161
Competitive Algorithms for Distributed Data Management
Bartal, Y., Fiat, A., & Rabani, Y. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1073 · Cited by 146
Self-citationCompetitive distributed file allocation
Awerbuch, B., Bartal, Y., & Fiat, A. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167142 · Cited by 121
Self-citationOn the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
Agarwala, R., Bafna, V., Farach-Colton, M., Paterson, M., & Thorup, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539795296334 · Cited by 114
Competitive algorithms for replication and migration problems
Black, D. L., & Sleator, D. D. (2018) · Figshare · doi:10.1184/r1/6604253 · Cited by 97
Distributed Paging for General Networks
Awerbuch, B., Bartal, Y., & Fiat, A. (1998) · Journal of Algorithms · doi:10.1006/jagm.1998.0924 · Cited by 55
Self-citationKoutsoupias, E., & Papadimitriou, C. H. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195245 · Cited by 55
A decomposition theorem and bounds for randomized server problems
Blum, A. L., Karloff, H. J., Rabani, Y., & Saks, M. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267772 · Cited by 42
The distributed k-server problem-a competitive distributed translator for k-server algorithms
Bartal, Y., & Rosen, A. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267756 · Cited by 25
Self-citationHeat and Dump: competitive distributed paging
Awerbuch, B., Bartal, Y., & Fiat, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366885 · Cited by 24
Self-citationOn page migration and other relaxed task systems
Bartal, Y., Charikar, M., & Indyk, P. (1997) · doi:10.5555/314161.314178 · Cited by 18
Self-citationPage migration with limited local memory capacity
Albers, S., & Koga, H. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60220-8_58 · Cited by 12
Randomized algorithms for metrical task systems
Irani, S., & Seiden, S. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60220-8_59 · Cited by 9
Cited by
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
Kleinberg, J., & Tardos, É. (2002) · Journal of the ACM · doi:10.1145/585265.585268 · Cited by 400
Network topology generators: degree-based vs. structural
Tangmunarunkit, H., Govindan, R., Jamin, S., Shenker, S., & Willinger, W. (2002) · Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/633025.633040 · Cited by 375
Approximation schemes for Euclidean k-medians and related problems
Arora, S., Raghavan, P., & Rao, S. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276718 · Cited by 341
Metadata
- Authors
- Bartal, Y.
- Venue
- Proceedings of 37th Conference on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc. Press
- Published
- 2002-12-23
- Pages
- 184-193
- OpenAlex
- W2114493937
- Cited by
- 635
- References
- 24
- FWCI
- 21.50
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.