[talks] M Bateni preFPO

[Melissa Lawson]

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.





 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20101206/a9f33559/attachment.html>