<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:st="" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 12 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.apple-style-span
        {mso-style-name:apple-style-span;}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Arial","sans-serif";
        color:blue;
        font-weight:normal;
        font-style:normal;
        text-decoration:none none;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'>Mohammad Hossein Bateni will present his preFPO on Monday December 13 at <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'>10:30AM in Room 302 (note room!).  The members of his committee are: <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'>Moses Charikar, advisor; Sanjeev Arora and MohammadTaghi Hajiaghayi (UMCP), <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'>readers; Bernard Chazelle and Rob Schapire, nonreaders.  Everyone is invited to <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'>attend his talk.  His abstract follows below.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'>--------------------------<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";color:blue'><o:p> </o:p></span></p><div><div><p class=MsoNormal><span style='font-size:8.0pt;font-family:"Arial","sans-serif"'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p></div><div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";color:#500050'><o:p> </o:p></span></p></div></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>The talk is based on joint works with Aaron Archer, MohammadTaghi Hajiaghayi, Howard Karloff, Philip Klein, Daniel Marx, and Claire Mathieu.<o:p></o:p></span></p></div><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:10.0pt'><br><br><o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>