23 citations · 146 across the 41 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.DS2013★ 2 cited
Approximation Algorithm for Sparsest k-Partitioning
Anand Louis, Konstantin Makarychev
Given a graph , the sparsest-cut problem asks to find the set of vertices which has the least expansion defined as $$ϕ_G(S) := \frac{w(E(S,\bar{S}))}{\min \set{w(S), w(\bar{…
cs.DS2013
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
We investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomial-time algorithm for -stable Max Cut instances with $γ\geq c\sqrt{\log n}\log\log…