[AMNSW] S. Arya, D. N. Mount, S. Netanyahu, R. Silverman, A. Y. Wu, An optimal algorithm for approximate nearest neighbor searching, , JACM.
[AE'98] P. Agarwal, J. Erickson, Geometric range searching and its relatives , 1998.
[AESW'90] P. Agarwal, H. Edelsbrunner, O. Schwartzkopf, E. Wezl, Euclidean minimum spanning trees and bichromatic closest pair, SoCG'90, pp. 203-210.
[AM'93] S. Arya, D. Mount, Approximate nearest neighbor searching, SODA'93
[AP'98] P. Agarwal, C. M. Procopiuc, Exact and approximation algorithms for clustering , SODA'98
[AV'99] R. I. Arriaga, S. Vempala, Algorithmic theories of learning , FOCS'99.
[Be'93] M. Bern, Approximate closest point queries in high dimensions, Information Processing Letters, 45 (1993), pp. 95-99.
[BG'97] A. Broder, S. Glassman, M. Manasse, G. Zweig, Syntactic clustering of the Web , WWW6.
[BOR'99] A. Borodin, R. Ostrovsky, Y. Rabani, Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces , STOC'99.
[BOR2'99] A. Borodin, R. Ostrovsky, Y. Rabani, Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems , STOC'99.
[BS'76] J. Bentley, M. Shamos, Divide and Conquer in Multidimensional Spaces, STOC'76, pp. 220-230.
[CG'99] M. Charikar, S. Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, FOCS'99.
[Ch'97] T. Chan, Approximate nearest neighbor queries revisited , SoCG'97.
[CH'67] T. Cover, P. Hart, Nearest Neighbor pattern classification, IEEE Transactions on Information Theory, 13 (1967), pp. 21-27.
[Cl'88] K. Clarkson, A randomized algorithm for closest-point queries , SICOMP'88.
[Cl'94] K. Clarkson, Algorithms for polytope covering and approximation, and for approximate closest-point queries
[Cl'97] K. Clarkson, Nearest Neighbor Queries in Metric Spaces , STOC'97
[CL'97] E. Cohen, D. Lewis Approximating matrix multiplication for pattern recognition tasks , SODA'97.
[DG'99] S. Dasgupta, A. Gupta, An elementary proof of the Johnson-Lindenstrauss lemma
[D'99] S. DasGupta, Learning mixtures of Gaussians , FOCS'99.
[DL'76] D. Dobkin, R. Lipton, Multidimensional Search Problems, SIAM Journal of Computing 5 (1976), pp. 181-186.
[BDB'95] M. W. Berry, S. Dumais, G. W. O'Brien, Using Linear Algebra for Intelligent Information Retrieval , SIAM Review 37:4 (1995).
[DGR'97] C. Duncan, M. Goodrich, E. Ramos, Efficient Approximation and Optimization Algorithms for Computational Metrology , SODA'97.
[E'92] D. Eppstein , Dynamic
Euclidean minimum spanning trees and extrema of binary functions ,
Discrete Computational Geometry 13 (1995), 111-122.
This paper contains a reduction from exact dynamic bichromatic closest pair to exact dynamic nearest neighbor, but apparently the same reduction works for approximate versions of the problems (thanks to David Eppstein for comments).
[E'97] D. Eppstein, Fast hierarchical clustering and other applications of dynamic closest pairs, SODA'98.
[FI'99] M. Farach-Colton, P. Indyk, Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings , FOCS'99.
[FG'90] T. Feder, D. Greene, Optimal Algorithms for Approximate Clustering, STOC'88.
[FM] P. Frankl, H. Maehara, The Johnson-Lindenstrauss Lemma and the Sphericity of Some Graphs, Journal of Combinatorial Theory B, 44(1988):355-362.
[Ga'94] B. Gartner, A Subexponential Algorithm for Abstract Optimization Problems,SIAM Journal of Computing 24 (1995), pp. 1018-1035.
[GBT'84] H. Gabow, J. Bentley, E. Tarjan, Scaling and Related Techniques for Geometry Problems, STOC'94, pp. 135-143.
[GGR'96] Goldreich, Goldwasser, Ron, Property Testing and its connection to Learning and Approximation , FOCS'96.
[GIM'99] A. Gionis, P. Indyk, R. Motwani, Similarity Search in High Dimensions via Hashing , VLDB'99.
[Go'85] T. Gonzales, Clustering to Minimize the Maximum Inter-Cluster Distance, Journal of Theoretical Computer Science 38 (1985), pp. 293-306.
[GH'99] N. Guttman-Beck, Hassin, Approximation algorithms for min-sum p-clustering, Discrete Applied Mathematics.
[HS'86] D. Hochbaum, D. Shmoys, A unified approach to approximate algorithms for bottleneck problems, Journal of the ACM, 33(1986), pp. 533-550.
[IKI'94] M. Inaba, N. Katoh, H. Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering, SOCG'94.
[I'98] P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces , FOCS'98.
[I'99] P. Indyk, Sublinear Time Algorithms for Metric Space Problems , STOC'99.
[I2'99] P. Indyk, Dimensionality Reduction Techniques for Proximity Problems , manuscript.
[I3'99] P. Indyk, Reductions among high dimensional problems, manuscript.
[I4'99] P. Indyk, A PTAS for clustering in metric spaces, FOCS'99.
[IM'98] P. Indyk, R. Motwani, Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality , draft of the final version. A preliminary version with slightly weaker results) appeared at STOC'98.
[JS'82] W. Johnson, G. Schechtman, Embedding l_p^m into l_1^n, Acta Mathematica 149 (1982), pp. 71-85 (for p=2 see the references therein).
[JV'99] K. Jain, V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems , FOCS'99.
[Kl'97] J. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions , STOC'97.
[KOR'98] E. Kushilevitz, R. Ostrovsky, Y. Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces , STOC'98.
[KR'99] S. Kolliopoulos, S. Rao, A nearly linear-time approximation scheme for the Euclidean k-median problem, ESA'99.
[LT'77] R. Lipton, E. Tarjan, Applications of planar separator theorem, FOCS'97, pp. 162-170.
[Ma'92] J. Matousek, On the distortion required for embedding finite metric spaces into normed spaces, Israel Journal of Mathematics 93 (1996), pp. 333-344.
[Ma'99] J. Matousek, On approximate geometric k-clustering , 1999.
[Me'93] S. Meiser, Point location in arrangements of hyperplanes, Information and Computation 106 (1993), pp. 286-303.
[MP'69] M. Minsky, S. Papert, Perceptrons, MIT Press, 1969.
[Ra'??] M. O. Rabin, ???
[Sch'98] Schulman, Clustering for Edge-Cost Minimization, 1999.
[Sch'99] Schulman, Scribe notes: lecture 4, ``Johnson-Lindenstrauss Embedding''
[Sh'75] I. Shamos, Geometric Complexity, STOC'75, pp. 224-233.
[SWY'74] G. Salton, A. Wong, S. Yang, A vector space model for automatic indexing, Communications of the ACM 18 (1975), pp. 613-620.
[Ya'82] A. C. C. Yao, On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems, SIAM Journal of Computing, 22 4 (1982), pp. 721-736.
[VK'98] de la Vega, Kenyon, Randomized Approximation Scheme for Metric MAX-CUT , FOCS'98.
[Var'98] K. Varadarajan, A two-approximation for bottleneck matching in MST time, personal communication, 1998.
[Va'84] P. Vaidya'84, A fast approximation for minimum spanning trees in k-dimensional space, FOCS'84, pp. 403-407.