{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:12Z","timestamp":1759639092715,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,11,19]],"date-time":"2016-11-19T00:00:00Z","timestamp":1479513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"crossref"}]},{"name":"U.S.-Israel BSF","award":["2010418"],"award-info":[{"award-number":["2010418"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["897\/13"],"award-info":[{"award-number":["897\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,1,31]]},"abstract":"<jats:p>\n            We introduce the\n            <jats:italic>st<\/jats:italic>\n            -cut version of the sparsest-cut problem, where the goal is to find a cut of minimum sparsity in a graph\n            <jats:italic>G<\/jats:italic>\n            (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) among those separating two distinguished vertices\n            <jats:italic>s<\/jats:italic>\n            ,\n            <jats:italic>t<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            . Clearly, this problem is at least as hard as the usual (non-\n            <jats:italic>st<\/jats:italic>\n            ) version. Our main result is a polynomial-time algorithm for the product-demands setting that produces a cut of sparsity\n            <jats:italic>O<\/jats:italic>\n            (\u221aOPT), where OPT \u2a7d 1 denotes the optimum when the total edge capacity and the total demand are assumed (by normalization) to be 1.\n          <\/jats:p>\n          <jats:p>\n            Our result generalizes the recent work of Trevisan [arXiv, 2013] for the non-\n            <jats:italic>st<\/jats:italic>\n            version of the same problem (sparsest cut with product demands), which in turn generalizes the bound achieved by the discrete Cheeger inequality, a cornerstone of Spectral Graph Theory that has numerous applications. Indeed, Cheeger\u2019s inequality handles graph conductance, the special case of product demands that are proportional to the vertex (capacitated) degrees. Along the way, we obtain an\n            <jats:italic>O<\/jats:italic>\n            (log |\n            <jats:italic>V<\/jats:italic>\n            |) approximation for the general-demands setting of sparsest\n            <jats:italic>st<\/jats:italic>\n            -cut.\n          <\/jats:p>","DOI":"10.1145\/2996799","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T14:01:46Z","timestamp":1479736906000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cheeger-Type Approximation for Sparsest\n            <i>st<\/i>\n            -Cut"],"prefix":"10.1145","volume":"13","author":[{"given":"Robert","family":"Krauthgamer","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Wagner","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,11,19]]},"reference":[{"volume-title":"robbers, and threatening skeletons: Padded decomposition for minor-free graphs. CoRR abs\/1311.3048","year":"2013","author":"Abraham Ittai","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729256"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00573-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IEEE International Conference on Computer Vision (ICCV)","volume":"1","author":"Yuri","year":"2001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.200"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886532"},{"key":"e_1_2_1_12_1","volume-title":"Spectral Graph Theory. CBMS Regional Conference Series in Mathematics","volume":"92","author":"Chung Fan R. K.","year":"1997"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502795"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0223-5"},{"volume-title":"Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization. 36--46","author":"Fakcharoenphol J.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488644"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62234"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2685-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995630"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90133-W"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63529"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_29_1","unstructured":"Daniel A. Spielman. 2012. Lecture Notes on Spectal Graph Theory Lecture 6. Retrieved from http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect06-12.pdf.  Daniel A. Spielman. 2012. Lecture Notes on Spectal Graph Theory Lecture 6. Retrieved from http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect06-12.pdf."},{"volume-title":"Is Cheeger-type approximation possible for nonuniform sparsest cut? CoRR abs\/1303.2730","year":"2013","author":"Trevisan Luca","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.244673"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262179"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2996799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2996799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:49Z","timestamp":1750273549000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2996799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,19]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2996799"],"URL":"https:\/\/doi.org\/10.1145\/2996799","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,11,19]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}