{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:34Z","timestamp":1781345674168,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-0098180CCR-0205594MSPA-MCS 0528414CCF-0514993ITR-0205594CCF 0832797CCR-0105533CCF-0515304CCF-0635357"],"award-info":[{"award-number":["CCR-0098180CCR-0205594MSPA-MCS 0528414CCF-0514993ITR-0205594CCF 0832797CCR-0105533CCF-0515304CCF-0635357"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0098180CCR-0205594MSPA-MCS 0528414CCF-0514993ITR-0205594CCF 0832797CCR-0105533CCF-0515304CCF-0635357"],"award-info":[{"award-number":["CCR-0098180CCR-0205594MSPA-MCS 0528414CCF-0514993ITR-0205594CCF 0832797CCR-0105533CCF-0515304CCF-0635357"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0121555"],"award-info":[{"award-number":["CCR-0121555"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>We give a<jats:italic>O<\/jats:italic>(\u221alog<jats:italic>n<\/jats:italic>)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in<jats:italic>R<\/jats:italic><jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>, whose proof makes essential use of a phenomenon called measure concentration.<\/jats:p><jats:p>We also describe an interesting and natural \u201capproximate certificate\u201d for a graph's expansion, which involves embedding an<jats:italic>n<\/jats:italic>-node expander in it with appropriate dilation and congestion. We call this an expander flow.<\/jats:p>","DOI":"10.1145\/1502793.1502794","type":"journal-article","created":{"date-parts":[[2009,4,15]],"date-time":"2009-04-15T13:37:07Z","timestamp":1239802627000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":273,"title":["Expander flows, geometric embeddings and graph partitioning"],"prefix":"10.1145","volume":"56","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, New Jersey"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Umesh","family":"Vazirani","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, California"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,4,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060675"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00573-5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_2_1_9_1","volume-title":"Flavors of Geometry","author":"Ball K.","unstructured":"Ball , K. 1997. An elementary introduction to modern convex geometry . In Flavors of Geometry . Mathematics Science Research Institute Publisher, vol. 31 . Cambridge Univ. Press , Cambridge, 1--58. Ball, K. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry. Mathematics Science Research Institute Publisher, vol. 31. Cambridge Univ. Press, Cambridge, 1--58."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90050-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109670"},{"key":"e_1_2_1_12_1","volume-title":"SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Chawla S.","unstructured":"Chawla , S. , Gupta , A. , and R\u00e4cke , H . 2005. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut . In SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, 102--111. Chawla, S., Gupta, A., and R\u00e4cke, H. 2005. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 102--111."},{"key":"e_1_2_1_13_1","unstructured":"Cheeger J. 1970. A lower bound for the smallest eigenvalue of the Laplacian. Probl. Analysis 195--199. Cheeger J. 1970. A lower bound for the smallest eigenvalue of the Laplacian. Probl. Analysis 195--199."},{"key":"e_1_2_1_14_1","volume-title":"CBMS Regional Conference Series in Mathematics","volume":"92","author":"Chung F. R. K.","year":"1997","unstructured":"Chung , F. R. K. 1997 . Spectral graph theory . CBMS Regional Conference Series in Mathematics , vol. 92 . Published for the Conference Board of the Mathematical Sciences, Washington, DC. Chung, F. R. K. 1997. Spectral graph theory. CBMS Regional Conference Series in Mathematics, vol. 92. Published for the Conference Board of the Mathematical Sciences, Washington, DC."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01193107"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132594"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02589549"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060674"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.07.009"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Goemans M. X.","year":"1998","unstructured":"Goemans , M. X. 1998 . Semidefinite programming and combinatorial optimization . In Proceedings of the International Congress of Mathematicians , Vol. III (Berlin, 1998). Doc. Math., 657--666 (electronic). Goemans, M. X. 1998. Semidefinite programming and combinatorial optimization. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998). Doc. Math., 657--666 (electronic)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_23_1","volume-title":"Algorithms and Combinatorics","volume":"2","author":"Gr\u00f6tschel M.","unstructured":"Gr\u00f6tschel , M. , Lov\u00e1sz , L. , and Schrijver , A . 1993. Geometric algorithms and combinatorial optimization, Second ed . Algorithms and Combinatorics , vol. 2 . Springer-Verlag, Berlin, Germany. Gr\u00f6tschel, M., Lov\u00e1sz, L., and Schrijver, A. 1993. Geometric algorithms and combinatorial optimization, Second ed. Algorithms and Combinatorics, vol. 2. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_84"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Karloff H. J. and Zwick U. 1997. A 7\/8-approximation algorithm for max 3sat&quest; In Proceedings of the 38th IEEE Foundations of Computer Science (FOCS). IEEE Computer Society Press Los Alamitos CA 406--415. Karloff H. J. and Zwick U. 1997. A 7\/8-approximation algorithm for max 3sat&quest; In Proceedings of the 38th IEEE Foundations of Computer Science (FOCS). IEEE Computer Society Press Los Alamitos CA 406--415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132574"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109669"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 10th International IPCO Conference. Lecture Notes in Computer Science","volume":"3064","author":"Lang K.","unstructured":"Lang , K. , and Rao , S . 2004. A flow-based method for improving the expansion or conductance of graph cuts . In Proceedings of the 10th International IPCO Conference. Lecture Notes in Computer Science , vol. 3064 . Springer-Verlag, Berlin, Germany, 325--337. Lang, K., and Rao, S. 2004. A flow-based method for improving the expansion or conductance of graph cuts. In Proceedings of the 10th International IPCO Conference. Lecture Notes in Computer Science, vol. 3064. Springer-Verlag, Berlin, Germany, 325--337."},{"key":"e_1_2_1_33_1","volume-title":"SODA '05: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Lee J. R.","year":"2005","unstructured":"Lee , J. R. 2005 . On distance scales, embeddings, and efficient relaxations of the cut cone . In SODA '05: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, USA, 92--101. Lee, J. R. 2005. On distance scales, embeddings, and efficient relaxations of the cut cone. In SODA '05: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, USA, 92--101."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_37_1","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"Matou\u0161ek J.","unstructured":"Matou\u0161ek , J. 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics , vol. 212 . Springer-Verlag , New York . Matou\u0161ek, J. 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer-Verlag, New York."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2005.04.003"},{"key":"e_1_2_1_39_1","volume-title":"SIAM Studies in Applied Mathematics","volume":"13","author":"Nesterov Y.","unstructured":"Nesterov , Y. , and Nemirovskii , A . 1994. Interior-point polynomial algorithms in convex programming . SIAM Studies in Applied Mathematics , vol. 13 . SIAM, Philadelphia, PA. Nesterov, Y., and Nemirovskii, A. 1994. Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, vol. 13. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1874-5849(03)80044-X"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77620"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_43_1","unstructured":"Shmoys D. S. 1995. Cut problems and their application to divide and conquer. In Approximation Algorithms for NP-Hard Problems D. Hochbaum Ed. PWS Publishing. Shmoys D. S. 1995. Cut problems and their application to divide and conquer. In Approximation Algorithms for NP-Hard Problems D. Hochbaum Ed. PWS Publishing."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502794","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1502793.1502794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:37Z","timestamp":1750253377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1502793.1502794"],"URL":"https:\/\/doi.org\/10.1145\/1502793.1502794","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}