Mohammad Hossein Bateni will present his preFPO on Monday December 13 at

10:30AM in Room 302 (note room!).  The members of his committee are:

Moses Charikar, advisor; Sanjeev Arora and MohammadTaghi Hajiaghayi (UMCP),

readers; Bernard Chazelle and Rob Schapire, nonreaders.  Everyone is invited to

attend his talk.  His abstract follows below.

--------------------------

Grouping a set of items into clusters according to their similarities is called clustering.  It is now a common technique in widely different applications in, e.g., bioinformatics, data mining, machine learning, and social network analysis.  Considerable effort has been put into study of the clustering techniques in recent years.

In this thesis, we introduce a new clustering paradigm, in which items to be classified are vertices of a graph.  Vertices have their own budgets and the goal is to cluster them such that the cost of (connections in) each cluster can be payed by the budget of its participants.  Furthermore, we want vertices in different clusters be in some sense far from each other.

We propose and analyze algorithms for two similar problems in this paradigm. The resulting guarantees lead to resolution of several network design questions.  We improve the approximation ratio for prize-collecting Steiner tree and TSP.  In addition, we present polynomial-time approximation schemes (PTAS's) for planar Steiner forest, planar multiway cut, and planar prize-collecting Steiner tree.

The talk is based on joint works with Aaron Archer, MohammadTaghi Hajiaghayi, Howard Karloff, Philip Klein, Daniel Marx, and Claire Mathieu.