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

Abstract

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

Created:
August 19, 2023
Modified:
October 23, 2023