203 citations · 288 across the 21 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.CC2013
The Complexity of Approximating Vertex Expansion
Anand Louis, Prasad Raghavendra, Santosh Vempala
We study the complexity of approximating the vertex expansion of graphs , defined as \[ Φ^V := \min_{S \subset V} n \cdot \frac{|N(S)|}{|S| |V \backslash S|}. \] We give…