Piotr Indyk
- 1.A. Borodin, R. Ostrovsky, Y. Rabani, "Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces", these proceedings. Google Scholar
Digital Library
- 2.M. Charikar, $. Guha, E. Taxdos, D. Shmoys, "A Constant Factor Approximation for the k-Median Problem", these proceedings. Google ScholarDigital Library
- 3.D.R. Cutting, D.R. Karger, J.O. Pedersen and J.W. Tukey, "Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections', SIGIR'92. Google ScholarDigital Library
- 4.E. Cohen, D. Lewis, "Approximating matrix multiw plication for pattern recognition tasks", SODA'97, pp. 682-691. Google ScholarDigital Library
- 5.F.Ergun, S.Karman, S.R. Kumar, R. Rubinfeld and M. Viswanathan, "Spo{-Checkers', STOC'98, pp. 259-268. Google ScholarDigital Library
- 6.O. Goldreich, S. Goldwasser and D. Ron, "Property testing and its connection to Learning and Approximation", FOCS'96, pp. 339-348. Google ScholarDigital Library
- 7.W. B. Frakes, R. Baeza-Yates, Information Retrieval- Data Structures and Algorithms, Prentice Hall, New Jersey, 1992. Google ScholarDigital Library
- 8.D. Gusfield, "Efficient methods for multiple sequence alignments with guaranteed error bounds", Bulletin of Mathematical Biology, 55 (1993), pp. 141-154.Google ScholarCross Ref
- 9.P. tndyk, "On Approximate Nearest Neighbors in Non-Euclidean Spaces", FOCS'98, pp. 148-154. Google ScholarDigital Library
- 10.P. lndyk, R. Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality', STOC'98, pp. 604-613. Google ScholarDigital Library
- 11.J. Kleinberg, "Two Algorithms for Nearest Ne~ighbor Search in High Dimensions", STOC'97, pp. 599-608. Google ScholarDigital Library
- 12.E. Kushilevitz, R. Ostrovsky, and Y. Rah~, "Efficien~ search for approximate nearest neighbor in high dimensional spaces", STOC'98, pp. 614-623. Google ScholarDigital Library
- 13.M. R. Korupolu, C. G. Plaxton, R. Rajamaran, "Analysis of a Local Search Heuristic for Facility Location Problems", SODA'98, pp. 1-10. Google ScholarDigital Library
- 14.S.R. Kosaraju, J.K. Park, C. Stein, "Long Tours and Short Supers~rings~, FOCS'94. Google ScholarDigital Library
- 15.J. Lin, J.S. Vitter, "e-Approximations with Minimum Packing Constraint Violation", STOC'92, pp. 771-782. Google ScholarDigital Library
- 16.J. Lin, J.S. Vitter, "Approximation Algorithms for Geometric Median Problems", IPL 44 (1992), pp. 245-249. Google ScholarDigital Library
- 17.R.L. Rivest, J. Vuillemin, "On recognizing graph properties from adjacency matrices", Theoretical Computer Science 3 (1976), pp. 371-384.Google ScholarCross Ref
- 18.B. Y. Wu, G. Lancia, V. Bafna, K Chao, R. Ravi, C. Y. Tang, "A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees", SODA'98, pp. 21-32. Google ScholarDigital Library
- 19.R. Wong, "Worst-case Analysis of Network Design Problem Heuristics~,.SIAM J. Alg.Discr. Meth. 1 (1980), pp. 51-63.Google ScholarCross Ref
Index Terms
- Sublinear time algorithms for metric space problems
Recommendations
Compressed dynamic tries with applications to LZ-compression in sublinear time and space
FSTTCS'07: Proceedings of the 27th international conference on Foundations of software technology and theoretical computer scienceThe dynamic trie is a fundamental data structure which finds applications in many areas. This paper proposes a compressed version of the dynamic trie data structure. Our data-structure is not only space efficient, it also allows pattern searching in o(|...
Estimating the weight of metric minimum spanning trees in sublinear-time
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingIn this paper we present a sublinear time (1 + ε)-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n-point metric space. The running time of the algorithm is Û(n/εO(1)). Since the full description of an n-...
Space-efficient parallel algorithms for combinatorial search problems
We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an n -node tree of height h under the assumption that a node can be accessed ...
Comments