[Colloquium] REMINDER: Research at TTIC: Yury Makarychev, TTIC

[Dawn Ellis]

When:     Friday, January 10th at Noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Who:       Yury Makarychev, TTIC Faculty

Title:        Bilu—Linial Stable Instances of Max Cut and Minimum Multiway
Cut

Abstract:

We investigate the notion of stability proposed by Bilu and Linial. We
obtain an exact polynomial-time  algorithm for gamma-stable Max Cut
instances with gamma > c sqrt{log n} log log n for some absolute constant c
> 0. Our algorithm is robust: it never returns an incorrect answer; if the
instance is gamma-stable, it finds the maximum cut, otherwise, it either
finds the maximum cut or certifies that the instance is not gamma-stable.
We prove that there is no robust polynomial-time algorithm for gamma-stable
instances of Max Cut when gamma it less than the best approximation factor
for Sparsest Cut with non-uniform demands. That suggests that solving
gamma-stable instances with gamma =o(sqrt{log n}) might be difficult or
even impossible.

Our algorithm is based on semidefinite programming. We show that the
standard SDP relaxation for Max Cut (with ell_2^2 triangle inequalities) is
integral if gamma > D(n), where D(n) is the least distortion with which
every n point metric space of negative type embeds into ell_1. On the
negative side, we show that the SDP relaxation is not integral when gamma <
D(n/2). Moreover, there is no tractable convex relaxation for gamma-stable
instances of Max Cut when gamma is less than the best approximation factor
for Sparsest Cut.

Our results significantly improve previously known results. The best
previously known algorithm for gamma-stable instances of Max Cut required
that gamma >  c\sqrt{n}  (for some c > 0)  [Bilu, Daniely, Linial, and
Saks]. No hardness results were known for the problem.

Additionally, we present an exact robust polynomial-time algorithm for
4-stable instances of Minimum Multiway Cut. We also study a relaxed notion
of weak stability and present algorithms for weakly stable instances of Max
Cut and Minimum Multiway Cut.

Joint work with Konstantin Makarychev and Aravindan Vijayaraghavan


***************************************
Research at TTIC Seminar Series

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140109/d54b9121/attachment.htm