{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:07Z","timestamp":1787340427702,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>This paper shows how to compute $O(\\sqrt{\\log n})$-approximations to the Sparsest Cut and Balanced Separator problems in $\\tilde{O}(n^2)$ time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222\u2013231]. Their algorithm uses semidefinite programming and requires $\\tilde{O}(n^{9.5})$ time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222\u2013231].<\/jats:p>","DOI":"10.1137\/080731049","type":"journal-article","created":{"date-parts":[[2010,1,22]],"date-time":"2010-01-22T18:11:24Z","timestamp":1264183884000},"page":"1748-1771","source":"Crossref","is-referenced-by-count":29,"title":["$O(\\sqrt{\\logn})$ Approximation to SPARSEST CUT in $\\tilde{O}(n^2)$ Time"],"prefix":"10.1137","volume":"39","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elad","family":"Hazan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satyen","family":"Kale","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,1,22]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"R4","unstructured":"S. Arora, E. Hazan, and S. Kale,\n                      The multiplicative weights method: A meta-algorithm and some applications\n                      , Theory Comput., submitted."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Kale,\n                      A combinatorial, primal-dual approach to semidefinite programs\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 227\u2013236.","DOI":"10.1145\/1250790.1250823"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Rao, and U. V. Vazirani,\n                      Expander flows, geometric embeddings and graph partitioning\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222\u2013231.","DOI":"10.1145\/1007352.1007355"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. A. Bencz\u00far and D. R. Karger,\n                      \n                        Approximating\n                        s\n                        -\n                        t\n                        minimum cuts in $\\tilde{O}(n^2)$ time\n                      \n                      , in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 47\u201355.","DOI":"10.1145\/237814.237827"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90050-8"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"R11","unstructured":"S. Chawla, A. Gupta, and H. R\u00e4cke,\n                      Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut\n                      , in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 102\u2013111."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Cheeger,\n                      A lower bound for the smallest eigenvalue of the Laplacian\n                      , in Problems in Analysis, Princeton University Press, Princeton, NJ, 1970, pp. 195\u2013199.","DOI":"10.1515\/9781400869312-013"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"F. Chung,\n                      Spectral Graph Theory\n                      , CBMS Regional Conf. Ser. in Math. 92, AMS, Providence, RI, 1997.","DOI":"10.1090\/cbms\/092"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"N. Garg and J. K\u00f6nemann,\n                      Faster and simpler algorithms for multicommodity flow and other fractional packing problems\n                      , in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 300\u2013309.","DOI":"10.1109\/SFCS.1998.743463"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Khandekar, S. Rao, and U. Vazirani,\n                      Graph partitioning using single commodity flows\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 385\u2013390.","DOI":"10.1145\/1132516.1132574"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792241175"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"R24","unstructured":"D. W. Matula,\n                      A linear time $2 + \\epsilon$ approximation algorithm for edge connectivity\n                      , in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 500\u2013504."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"L. Orecchia, L. J. Schulman, U. V. Vazirani, and N. K. Vishnoi,\n                      On partitioning graphs via single commodity flows\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 461\u2013470.","DOI":"10.1145\/1374376.1374442"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"S. A. Plotkin, D. B. Shmoys, and \u00c9. Tardos,\n                      Fast approximation algorithms for fractional packing and covering problems\n                      , in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 495\u2013504.","DOI":"10.1109\/SFCS.1991.185411"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77620"},{"key":"R29","unstructured":"D. S. Shmoys,\n                      Cut problems and their application to divide and conquer\n                      , in Approximation Algorithms for NP-hard Problems, PWS, Boston, 1995."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"V. Vazirani,\n                      Approximation Algorithms\n                      , Springer-Verlag, Berlin, 2002.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"R31","unstructured":"N. E. Young,\n                      Randomized rounding without solving the linear program\n                      , in Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995, pp. 170\u2013178."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080731049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:39Z","timestamp":1787337279000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080731049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080731049"],"URL":"https:\/\/doi.org\/10.1137\/080731049","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}