[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.