Lorenzo Orecchia
Leonard J. Schulman
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.
- S. Arora, E. Hazan, and S. Kale. O(√log n) approximation to sparsest cut in $\tildeO(n^2)$ time. Proceedings, IEEE Symposium on Foundations of Computer Science, 00:238--247, 2004. Google Scholar
Digital Library
- S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. In STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 227--236, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 222--231, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- R. Bhatia. Matrix Analysis (Graduate Texts in Mathematics). Springer, 1996.Google Scholar
- F. R. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, 1997.Google Scholar
- N. R. Devanur, S. A. Khot, R. Saket, and N. K. Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. In STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 537--546, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- A. V. Goldberg and S. Rao. Beating the flow decomposition barrier. Journal of the ACM (JACM), 45:783--797, 1998. Google ScholarDigital Library
- G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20:359--392, 1999. Google ScholarDigital Library
- R. Khandekar, S. Rao, and U. Vazirani. Graph partitioning using single commodity flows. In STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 385--390, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- R. M. Khandekar, S. Khot, L. Orecchia, and N. K. Vishnoi. On a cut-matching game for the sparsest cut problem. Technical Report EECS-2007-177, EECS Department, University of California, Berkeley, CA, 2007.Google Scholar
- T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999. Google ScholarDigital Library
- C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982. Google ScholarDigital Library
- D. Shmoys. Cut problems and their application to divide and conquer. In D. Hochbaum, editor, Approximation algorithms for NP-hard problems, pages 192--235. PWS Publishing Co., Boston, MA, USA, 1996. Google ScholarDigital Library
Index Terms
- On partitioning graphs via single commodity flows
Recommendations
Graph partitioning using single commodity flows
We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log2 n) factor in Õ(m + n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that ...
Expander flows, geometric embeddings and graph partitioning
We give a O(√log n)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with ...
Graph partitioning using single commodity flows
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe show that the sparsest cut in graphs can be approximated within O(log2 n) factor in Õ(n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n2). Our algorithm ...
Comments