Eva Tardos, Cornell University, visiting UCB
Approximation algorithms for some clustering problems
Clustering problems arise in a wide range of application
settings from clustering documents to placing centers in
networks. The applications mentioned above give rise to a
number of related hard algorithms problems, where the aim
is to partition a given set of points into clusters so that
the points within a cluster are relatively close with
respect to some measure.
Approximation algorithms provide a framework to develop algorithms
for such problems that provide solutions that are provably
close to optimal. In this talk we shall discuss some of the
approximation algorithms for these problems.