Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2008 | public
Book Section - Chapter

On partitioning graphs via single commodity flows


In this paper we obtain improved upper and lower bounds for the best approximation factor for Sparsest Cut achievable in the cut-matching game framework proposed in Khandekar et al. [9]. We show that this simple framework can be used to design combinatorial algorithms that achieve O(log n) approximation factor and whose running time is dominated by a poly-logarithmic number of single-commodity max-flow computations. This matches the performance of the algorithm of Arora and Kale [2]. Moreover, we also show that it is impossible to get an approximation factor of better than Ω(√log n) in the cut-matching game framework. These results suggest that the simple and concrete abstraction of the cut-matching game may be powerful enough to capture the essential features of the complexity of Sparsest Cut.

Additional Information

© 2008 ACM. Supported by NSF Awards CCF-0635401, CCF-0515304, CCF-0635357 and CCR-0121555. Supported by NSA Award H98230-06-1-0074, NSF Award CCF-0515342. Supported by NSF Award CCF-0635401. Part of this work was done when author was visiting UC Berkeley and is supported by NSF Grant CCF-0635401.

Additional details

August 19, 2023
October 23, 2023