Abstract:
One of the fundamental problems in pattern recognition and information processing is that of clustering a large data set into a small number of meaningful groups. There are many different approaches to clustering and different optimization criteria.

In this talk we will concentrate on one popular clustering method called k-means clustering. Although no efficient algorithm is known for this problem, we will discuss the performance of two known heuristics. The first provides only a locally optimal solution, and the second is based on local-search. We will present a proof that the combination of these two heuristics produces an efficient and practical approximation algorithm for k-means clustering.

Biography:
David Mount is a professor in the Department of Computer Science at the University of Maryland with a joint appointment in the Institute for Advanced Computer Studies. He received his Ph.D. from Purdue University in Computer Science in 1983. His primary research interests include the design, analysis and implementation of data structures and algorithms for geometric problems, particularly problems with applications in image processing, pattern recognition, information retrieval, and computer graphics. He is an associate editor for Pattern Recognition. Currently he is a visiting professor at the Hong Kong University of Science and Technology.