{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:58:05Z","timestamp":1760245085801,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"10","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"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":["MSPA-MCS 0528414CCF 0514993ITR 0205594CCF-0515304CCF-0635357CCF-0635401ITR CCR-0121555"],"award-info":[{"award-number":["MSPA-MCS 0528414CCF 0514993ITR 0205594CCF-0515304CCF-0635357CCF-0635401ITR CCR-0121555"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["MSPA-MCS 0528414CCF 0514993ITR 0205594CCF-0515304CCF-0635357CCF-0635401ITR CCR-0121555"],"award-info":[{"award-number":["MSPA-MCS 0528414CCF 0514993ITR 0205594CCF-0515304CCF-0635357CCF-0635401ITR 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":["Commun. ACM"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1145\/1400181.1400204","type":"journal-article","created":{"date-parts":[[2008,9,23]],"date-time":"2008-09-23T13:37:59Z","timestamp":1222177079000},"page":"96-105","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Geometry, flows, and graph-partitioning algorithms"],"prefix":"10.1145","volume":"51","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[{"name":"UC, Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Umesh","family":"Vazirani","sequence":"additional","affiliation":[{"name":"UC, Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1007\/BF02579166"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/FOCS.2004.1"},{"key":"e_1_2_1_3_1","volume-title":"Multiplicative weights method: a meta-algorithm and its applications---a survey","author":"Arora S.","year":"2005","unstructured":"Arora , S. , Hazan , E. , and Kale , S . Multiplicative weights method: a meta-algorithm and its applications---a survey , 2005 . Arora, S., Hazan, E., and Kale, S. Multiplicative weights method: a meta-algorithm and its applications---a survey, 2005."},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1250790.1250823"},{"issue":"1","key":"e_1_2_1_5_1","first-page":"1","article-title":"Euclidean distortion and the sparsest cut. J. Amer Math","volume":"21","author":"Arora S.","year":"2008","unstructured":"Arora , S. , Lee , J. R. , and Naor , A . Euclidean distortion and the sparsest cut. J. Amer Math , Soc. , 21 ( 1 ): 1 -- 21 2008 (Electronic). Arora, S., Lee, J. R., and Naor, A. Euclidean distortion and the sparsest cut. J. Amer Math, Soc., 21(1):1--21 2008 (Electronic).","journal-title":"Soc."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1007352.1007355"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/1070432.1070447"},{"key":"e_1_2_1_8_1","first-page":"195","volume-title":"Problem in Analysis","author":"Cheeger J.","year":"1970","unstructured":"Cheeger , J. A lower bound for the smallest eigenvalue of the Laplacian . In Problem in Analysis , pages 195 -- 199 , 1970 . Cheeger, J. A lower bound for the smallest eigenvalue of the Laplacian. In Problem in Analysis, pages 195--199, 1970."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Congress of Mathematicians","volume":"666","author":"Goemans M. X.","year":"1998","unstructured":"Goemans , M. X. Semidefinite programming and combinatorial optimization . In Proceedings of the International Congress of Mathematicians , Vol. Ill (Berlin, 1998), pages 657-- 666 , 1998 (electronic). Goemans, M. X. Semidefinite programming and combinatorial optimization. In Proceedings of the International Congress of Mathematicians, Vol. Ill (Berlin, 1998), pages 657--666,1998 (electronic)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/227683.227684"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.5555\/305219.305248"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/1132516.1132574"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.5555\/1070432.1070446"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/331524.331526"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1109\/sfcs.1994.365733"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1374376.1374442"},{"key":"e_1_2_1_17_1","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Shmoys D. S.","year":"1995","unstructured":"Shmoys , D. S. Cut problems and their application to divide and conquer . In D. S. Hochbaum, ed., Approximation Algorithms for NP-Hard Problems . PWS Publishing , 1995 . Shmoys, D. S. Cut problems and their application to divide and conquer. In D. S. Hochbaum, ed., Approximation Algorithms for NP-Hard Problems. PWS Publishing, 1995."},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Comput","first-page":"134","volume-title":"Graph-Theoretic Concepts in Computer Science (Staffelstein","author":"Sinclair A.","year":"1987","unstructured":"Sinclair , A. and Jerrum , M . Approximate counting, uniform generation and rapidly mixing Markov chains (extended abstract) . In Graph-Theoretic Concepts in Computer Science (Staffelstein , 1987 ), volume 314 of Lecture Notes in Comput . Sci., pages 134 -- 148 , Berlin, 1988. Springer . Sinclair, A. and Jerrum, M. Approximate counting, uniform generation and rapidly mixing Markov chains (extended abstract). In Graph-Theoretic Concepts in Computer Science (Staffelstein, 1987), volume 314 of Lecture Notes in Comput. Sci., pages 134--148, Berlin, 1988. Springer."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1400181.1400204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1400181.1400204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:54Z","timestamp":1750255074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1400181.1400204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":18,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1400181.1400204"],"URL":"https:\/\/doi.org\/10.1145\/1400181.1400204","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2008-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}