• Can someone kindly help clarify as to exactly what is the generally accepted definition of the "sparsest cut" problem for a graph?

    (Isn't the set which achieves the Cheeger constant for a graph, the same set which would be said to have the "sparsest cut"? http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29)

  • I guess one can think of the ARV algorithm to be giving a polynomial time $O(\sqrt{log (n)})$-approximation algorithm to get the Cheeger constant. Right?

  • Now consider the quantity, $N-cut = \sum_{i=1}^{k} \frac { E(S_i,V /\ S_i)}{Vol(S_i) }$ where $S_i$ are $k$ disjoint sets partitioning the graph and $Vol(S_i)$ is the sum of the degrees of the vertices in $S_i$.

    Does the ARV algorithm automatically also give an approxmation algorithm for finding the sets $S_i$ which will give the lowest value of N-cut? (if not, then what is the best known answer to this?)

This paper I believe gives the best known approximation algorithm to the Cheeger constant, http://www.cs.princeton.edu/~arora/pubs/AHK.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.