Balanced Cut: Beyond the Worst-Case Analysis
Konstantin Makarychev
Redmond
Abstract.
Balanced Cut problem asks to partition vertices of a graph into two roughly equal pieces S and T so as to minimize the number of edges crossing the boundary between S and T. My lecture will consist of two parts. In the first part, I will give a brief tutorial on Balanced Cut. I will define the problem and describe some classic algorithms for it. These algorithms give poly-logarithmic approximation in the worst case. In the second part, we will discuss alternatives to the worst case model. I will present a new semi-random model for “real-life” instances of Balanced Cut and give a constant factor approximation algorithm for such instances. The second part is based on a joint work with Yury Makarychev and Aravindan Vijayaraghavan.