[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SERIES:
 
 
Tuesday, April 1, 2014
3:00 pm
Ryerson 251
Note not-standard day and time
 
Konstantin Makarychev
Microsoft Research
Reaearch.microsoft.com/en/people/komakary
 
Title: Constant Factor Approximation for Balanced Cut in the PIE Model
Speaker: Konstantin Makarychev, Microsoft Research
 
Abstract:
We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V partitioned into two clusters L and R of equal size. Let G be an arbitrary graph on V with no edges between L and R. Let E_random be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under permutation of vertices in L and in R). Then we say that G + E_random is a graph with permutation-invariant random edges.
 
We present an approximation algorithm for the Balanced Cut problem that finds a balanced cut of cost O(|E_random|) + n polylog(n) in this model. In the most interesting regime, this is a constant factor approximation with respect to the cost of the planted cut.
 
Joint work with: Yury Makarychev and Aravindan Vijayaraghavan
 
Hosts: Prof. Razborov and Prof. Makarychev
(Refreshments will be served prior to the talk in Ryerson 255 @ 2:30)
 
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140319/cc10a95c/attachment.htm