Bypassing the embedding: algorithms for low dimensional metrics. (English) Zbl 1192.68918
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 281-290, electronic only (2004).
MSC:
| 68W25 | Approximation algorithms |
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.]] 10.1137/S0097539792224474 · Zbl 0818.90147 |
| [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.]] |
| [3] | S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753-782, 1998.]] 10.1145/290179.290180 · Zbl 1064.90566 |
| [4] | S. Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Mathematical Programming, 97(1-2):43-69, 2003.]] · Zbl 1035.90113 |
| [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.]] 10.1145/276698.276718 |
| [6] | P. Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4):429-448, 1983.]] · Zbl 0597.54015 |
| [7] | B. Awerbuch, A. B. Noy, N. Linial, and D. Peleg. Improved routing strategies with succinct tables. J. Algorithms, 11(3):307-341, 1990.]] 10.1016/0196-6774(90)90017-9 · Zbl 0724.68004 |
| [8] | B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discret. Math., 5(2):151-162, 1992.]] 10.1137/0405013 · Zbl 0762.68025 |
| [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.]] |
| [10] | Y. Bartal. On approximating arbitrary metrices by tree metrics. In 30th Annual ACM Symposium on Theory of Computing, pages 161-168. ACM, 1998.]] 10.1145/276698.276725 · Zbl 1029.68951 |
| [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.]] 10.1006/jcss.1999.1690 · Zbl 0958.68047 |
| [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.]] · Zbl 0987.05086 |
| [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.]] 10.1145/200836.200853 · Zbl 0886.68078 |
| [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.]] |
| [15] | K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom., 22(1):63-93, 1999.]] · Zbl 0994.54501 |
| [16] | L. J. Cowen. Compact routing with minimum stretch. J. Algorithms, 38(1):170-183, 2001.]] 10.1006/jagm.2000.1134 · Zbl 0969.68180 |
| [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.]] 10.1145/277697.277702 |
| [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.]] |
| [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.]] 10.1145/780542.780608 · Zbl 1192.68977 |
| [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.]] · Zbl 1006.68542 |
| [21] | C. Gavoille and D. Peleg. Compact and localized distributed data structures. Distrib. Comput., 16(2-3):111-120, 2003.]] 10.1007/s00446-002-0073-5 · Zbl 1448.68225 |
| [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.]] · Zbl 0987.05083 |
| [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.]] · Zbl 1058.65028 |
| [24] | A. Gupta, R. Krauthgamer, and J. Lee. Bounded geometries, fractals and low-distortion embeddings. In Foundations of Computer Science, 2003.]] |
| [25] | S. Har-Peled and S. Mazumdar. Coresets for k-means and \(k\)-median clustering and their applications. In These Proceedings, 2004.]] 10.1145/1007352.1007400 |
| [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.]] |
| [27] | P. Indyk. Algorithms for dynamic geometric problems over data streams. In These Proceedings, 2004.]] 10.1145/1007352.1007413 · Zbl 1192.68179 |
| [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.]] 10.1145/509907.510013 |
| [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.]] |
| [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.]] |
| [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.]] · Zbl 1029.30014 |
| [33] | U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285-307, 2001.]] · Zbl 1024.54013 |
| [34] | N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995.]] · Zbl 0827.05021 |
| [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.]] 10.1137/S0097539796309764 · Zbl 0940.68062 |
| [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.]] · Zbl 0959.68042 |
| [38] | D. Peleg. Proximity preserving labeling schemes. Journal of Graph Theory, 33:167-176, 2000.]] · Zbl 0945.05052 |
| [39] | D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510-530, 1989.]] 10.1145/65950.65953 · Zbl 0900.68262 |
| [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.]] · Zbl 0837.90103 |
| [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.]] 10.1145/276698.276868 · Zbl 1027.68651 |
| [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.]] 10.1145/380752.380798 · Zbl 1323.05126 |
| [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.]] 10.1145/378580.378581 |
| [45] | L. Trevisan. When Hamming meets Euclid: The approximability of geometric TSP and steiner tree. SICOMP: SIAM Journal on Computing, 30, 2000.]] 10.1137/S0097539799352735 · Zbl 0963.68080 |
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.
