CMU Theory Lunch: Or Sheffet, Clustering under Stability Assumptions/title>  <link rel="stylesheet" href="lunch-main.css"/> </head> <body> <div id="page"> <div id="page_contents">  <div id="header"> <div id="page_title">Theory Lunch</div> <div id="scs_logo"><img src="cmu-scs.gif" alt="School of Computer Science, Carnegie Mellon University" width="290px" border="0" /></div> </div> <div id="main_container">  <div id="sched_header"> Clustering under Stability Assumptions </div> <div id="abs_talk_speaker">Or Sheffet </a> </div> <div id="abs_date">Feb 03, 2010</div>  <div id="abs">  ABSTRACT:Clustering is a notoriously hard task. Recently, several papers have suggested a new approach to clustering, motivated by examining natural assumptions that arise in practice, or that are made implicitly by many standard algorithmic approaches. These assumptions concern various measures of stability of our given clustering instance. The work of Bilu and Linial refers to stability with respect to perturbations in the metric space. The work of Balcan, Blum and Gupta refers to stability with respect to approximations of the quantitative objective chosen for our clustering instance. <p> Our work improves on these results in several important ways. For the Bilu-Linial assumption, we show that for center-based clustering objectives (such as $k$-median or $k$-means) we can efficiently find the optimal clustering assuming only stability to constant-magnitude perturbations of the underlying metric. For the approximation assumption of Balcan et al., we relax their condition to require good behavior only for ``natural'' approximations of the objective: specifically, only approximations in which each point is assigned to its nearest center. We show that for the $k$-median objective, under the assumption that all such approximations yield the same partitioning, it is possible to obtain an optimal solution in polynomial time.<br> This is joint work with Pranjal Awasthi and Avrim Blum. </p> </div>  </body>