Finding small sparse cuts by random walk
Refereed conference paper presented and published in conference proceedings


Times Cited
Altmetrics Information
.

Other information
AbstractWe study the problem of finding a small sparse cut in an undirected graph. Given an undirected graph G = (V,E) and a parameter k ≤ |E|, the small sparsest cut problem is to find a set S ⊆ V with minimum conductance among all sets with volume at most k. Using ideas developed in local graph partitioning algorithms, we obtain the following bicriteria approximation algorithms for the small sparsest cut problem: - If there is a set U ⊆ V with conductance φ and vol(U) ≤ k, then there is a polynomial time algorithm to find a set S with conductance O(√φ/ε) and vol(S) ≤ k
1+ε for any ε > 1/k. - If there is a set U ⊆ V with conductance φ and vol(U) ≤ k, then there is a polynomial time algorithm to find a set S with conductance and O(√φ log k/ε) and vol(S) ≤ (1 + ε)k for any ε > 2 log k/k. These algorithms can be implemented locally using truncated random walk, with running time almost linear to k. © 2012 Springer-Verlag.
All Author(s) ListKwok T.C., Lau L.C.
Name of Conference15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012
Start Date of Conference15/08/2012
End Date of Conference17/08/2012
Place of ConferenceCambridge, MA
Country/Region of ConferenceUnited States of America
Year2012
Month8
Day28
Volume Number7408 LNCS
PublisherSpringer Verlag
Place of PublicationGermany
Pages615 - 626
ISBN9783642325113
ISSN0302-9743
LanguagesEnglish-United Kingdom

Last updated on 2021-26-01 at 23:56