Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.   Geometric Approximation via Coresets, manuscript, 2005

Alon, N., Dar, S., Parnas, M., Ron, D.,   Testing of Clustering, Proc. 41st FOCS (2000)

Alon, N., Spencer, J.   The probabilistic Method, Wiley (2000)

Alon, N., Sudakov, B.,   On Two Segmentation Problems, Journal of Algorithms 33, 173--184 (1999)

Arora, S., Raghavan, P., Rao, S.,   Approximation schemes for Euclidean k-medians and related problems, Proc. 13th STOC (1998)

Badoiu, M., Clarkson, K. L.,   Smaller core sets for balls, Proc. 14th SODA (2003).

Badoiu, M., Har-Peled, S., Indyk, P.   Approximate Clustering via Core-Sets, Proc. 34th STOC (2002), 250-257.

De la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.   Approximation Schemes for Clustering Problems, Proc. 35th STOC (2003), 50-58.

Gonzalez, T.F.,   Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci. 38, 2-3, 293--306 (1985).

Har-Peled, S., Kushal, A.   Smaller coresets for k-median and k-means clustering, Proc. 21st SOCG (2005).

Har-Peled, S., Mazumdar, S.   Coresets for k-means and k-median clustering and their applications, Proc. 36th STOC (2004), 291-300.

Inaba, M., Katoh, N., Imai, H.   Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based k-Clustering, Proc. 10th SoCG (1994), 332--339.

Kleinberg, J., Papadimitriou, C., Prabhakar, R.,   Segmentation Problems, Proc. 13th STOC (1998), 473--482.

Kolliopoulos, S. G., Rao, S.,   A nearly linear-time approximation scheme for the Euclidean k-media problem, Proc. 7th ESA (1999)

Kumar, A., Sabharwal, Y.,Sen, S.   A simple linear time (1+epsilon)-approximation algorithm for k-means clustering in any dimensions, Proc. 45th FOCS (2004), 454-462.

Kumar, A., Sabharwal, Y.,Sen, S.   Linear time algorithms for clustering problems in any dimensions, Manuscript, 2005.

Mishra, N., Oblinger, D., Pitt, L.   Sublinear time approximate clustering, Proc. 12th SODA (2001)

Ostrovsky, R., Rabani, Y.   Polynomial time approximation schemes for geometric k-clustering, JACM, 49 (2002), 139-156.

Beier, R., Vocking, B., (o' in Vocking name with two-dot accent)   Probabilistic analysis of Knapsack core algorithms, Proc. 14th SODA, 468--477 (2004)

Spielman, D., Teng, S.H.,   Smoothed Analysis of Algorithms: Why the simplex algorithm usually takes polynomial time, Proc. 33rd STOC, (2001)

Spielman, D., Teng, S.H.,   Smoothed Analysis: Motivation and discrete models, Proc. WADS, LNCS, Springer-Verlag (2003)

Charikar, M., Guha, S., Tardos, E., Shmoys, D.,   A constant factor approximation algorithm for the k-median problem, Proc. 31st STOC (1999) (This paper deals with approximation algorithms for k-median on general metrics)

Har-Peled, S.,   Clustering Motion, Proc. 42nd FOCS, 84--93, 2001 (this paper deals with dynamic clustering when the points are moving in space)

Har-Peled, S., Varadarajan, K. R.,   Projective clustering in high dimensions using core-sets, Proc. 22nd SoCG (2002) (using core-set ideas to cluster points by k dimensional flats)

Kearns, M., Ron, D.,  Testing problems with sub-learning sample complexity, Journal of Computer and System Sciences, 61, 428--456 (2000), (this link can be used to relate selfadjusting algs to learning functions on domains with unknown distribution. the idea in this paper is to test whether a concept class H contains a function that is close to some f (not to actually find it). )