Clustering for edge-cost minimization (extended abstract)

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. Arabie, L. J. Hubert, and G. De Soete, editors. Clustering and Classification. World Scientific, 1996.
	2	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
	3	Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
	4	Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
	5	Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
	6	J. P. Benz~cri. Construction d'une classification ascendante hi~rarchique par la recherche en chaine des voisins r~ciproques. Les Cahiers de l'Analyse des Danndes, VII(2):209-218, 1982.
	7	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	8	E. Boros , P. L. Hammer, On clustering problems with connected optima in Euclidean spaces, Discrete Mathematics, v.75 n.1-3, p.81-88, 1989 [doi>10.1016/0012-365X(89)90080-0]
	9	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
	10	R. M. Cormack. A review of classification. J. Roy. Star. Soc. A, 134:321-367, 1971.
	11	H. E. Day and H. Edelsbrunner. Efficient algorithms for agglomerative hierarchical clusteriag methods. Journal of Classification, 1:7-24, 1984.
	12	W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures & Algorithms, v.8 n.3, p.187-198, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U]
	13	W. Fernandez de la Vega and M. Karpinski. Polynomial time approximation of dense weighted instances of maxcut. manuscript.
	14	W. Fernandez de la Vega , Claire Kenyon, A Randomized Approximation Scheme for Metric MAX-CUT, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.468, November 08-11, 1998
	15	P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
	16	A. W. F. Edwards and L. L. Cavalli-Sforza. A method for cluster analysis. Biometrics, 21:362-375, 1965.
	17	W. D. Fisher. On grouping for maximum homogeneity. Journal of the American Statistical Association, 53:789-798, 1958.
	18	R. M. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theor. Cornput. Sci., 1:237-267, 1976.
	19	'A. D. Gordon. Classification. Chapman and Hall, 1981.
	20	J. C. Gower. A comparison of some methods of cluster analysis. Biometrics, 23:623-637, 1967.
	21	C. Greene and D. J. Kleitman. Proof techniques in the theory of finite sets. In G.-C. Rota, editor, Studies in Combinatorics. The Mathematical Association of America, 1978.
	22	P. Hansen, B. Jaumard, and N. Mladenovid. Minimum sum of squares clustering in a low dimensional space. Journal of Classification, 15:37-55, 1998.
	23	John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
	24	Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178042]
	25	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	26	Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
	27	R. C. Jancey. Multidimensional group analysis. Australian Journal of Botany, 14:127-130, 1966.
	28	N. Jardine and R. Sibson. Mathematical Taxonomy. Wiley, 1971.
	29	W. B. Johnson and J. Lindenstrauss. Extensions of Lip~ schitz mappings into a Hfibert space. Contemp. Math., 26:189-206, 1984.
	30	J. Juan. Programme de classification hi~rarchique par l'algorithme de la recherche en chaine des voisins r~ciproques. Les Cahiers de l'Analyse des Dann4es, Vii(2):229-225, 1982.
	31	R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.
	32	N. E. Kiseleva, I. B. Muchnik, and S. G. Novikov. Stratified samples in the problem of representative sampling. Automation and Remote Control, 47(5):684-693, 1986.
	33	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
	34	N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. In Proc. 35'th Annual Symposium on Foundations of Computer Science, pages 577-591. IEEE Press, 1994.
	35	J. MacQueen. Some methods for classification and analysis of multivariate observations. In L. M. Le Cam and J. Neyman, editors, Proceedings of the 5'th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281-297. U. California Press, 1967.
	36	G. J. McLachlan and K. E. Basford. Mixture Models: Inference and Applications to Clustering. Marcel Dekker, 1988.
	37	B. Mirkin. Mathematical Classification and Clustering. Kluwer, 1996.
	38	B. G. Mirkin and I. Muchnik. Clustering and multidimensional scaling in Russia (1960-1990): a review. In P. Arabie, L. J. Hubert, and G. De Soete, editors, Clustering and Classification, pages 295-339. World Scientific, 1996.
	39	J. Neyman. On the two different aspects of the representative model: the method of stratified sampling and the method of purposive selection. J. R. Statis. Soc., 97:558-606, 1934.
	40	D. Pollard. Quantization and the method of k-means. iEEE Trans. In/orm. Theory, IT-28:199-205, March 1982.
	41	M J Sabin , R M Gray, Global convergence and empirical consistency of the generalized Lloyd algorithm, IEEE Transactions on Information Theory, v.32 n.2, p.148-155, March 1986 [doi>10.1109/TIT.1986.1057168]
	42	S. Sahni and T. Gonzales. P-complete problems and approximate solutions. In 15th Annual Symposium on Switching and Automata Theory, pages 28-32. IEEE, 1974.
	43	A. J. Scott and M. J. Symons. On the Edwards and Cavalli-Sforza method of cluster analysis. Biometrics, 27:217-219, 1971.
	44	Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
	45	M. I. Shlezinger. On unsupervised pattern recognition. In V. M. Glushkov, editor, Reading Automata, pages 62-70. Naukova Dumka, 1965.
	46	R. R. Sokal and P. H. A. Sneath. Principles of Numerical Taxonomy. Freeman, 1963.
	47	J. van Ryzin, editor. Classification and Clustering. Academic Press, 1977.
	48	J. H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58:236-244, 1963.