BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Aida Khajavirad (Rutgers University) DTSTART:20200707T183000Z DTEND:20200707T190000Z DTSTAMP:20260423T021858Z UID:DOTs/19 DESCRIPTION:Title: Th e ratio-cut polytope and K-means clustering\nby Aida Khajavirad (Rutge rs University) as part of Discrete Optimization Talks\n\n\nAbstract\nWe in troduce the ratio-cut polytope defined as the convex hull of ratio-cut vec tors corresponding to all partitions of $n$ points in $R^m$ into at most $ K$ clusters. This polytope is closely related to the convex hull of the fe asible region of a number of clustering problems such as K-means clusterin g and spectral clustering. We study the facial structure of the ratio-cut polytope and derive several types of facet-defining inequalities. We then consider the problem of K-means clustering and introduce a novel linear pr ogramming (LP) relaxation for it. Subsequently\, we focus on the case of t wo clusters and derive sufficient conditions under which the proposed LP r elaxation recovers the underlying clusters exactly. Namely\, we consider t he stochastic ball model\, a popular generative model for K-means clusteri ng\, and we show that if the separation distance between cluster centers s atisfies $\\Delta > 1+\\sqrt 3$\, then the LP relaxation recovers the plan ted clusters with high probability. This is a major improvement over the o nly existing recovery guarantee for an LP relaxation of K-means clustering stating that recovery is possible with high probability if and only if $\ \Delta > 4$. Our numerical experiments indicate that the proposed LP relax ation significantly outperforms a popular semidefinite programming relaxat ion in recovering the planted clusters.\n LOCATION:https://researchseminars.org/talk/DOTs/19/ END:VEVENT END:VCALENDAR