{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:02Z","timestamp":1787340842349,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We study graph partitioning problems from a min-max perspective, in which an input graph on $n$ vertices should be partitioned into $k$ parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the $k$ parts need to be of equal size, and where they must separate a set of $k$ given terminals. We consider a common generalization of these two problems, and design for it an $O(\\sqrt{\\log n\\log k})$ approximation algorithm. This improves over an $O(\\log^2 n)$ approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly $O(k\\log n)$ approximation for the first version that follows from other previous work. We also give an $O(1)$ approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph $G$ and the goal is to find a nonempty set $S\\subseteq V$ of size $|S| \\leq \\rho n$ with minimum edge expansion. We give an $O(\\sqrt{\\log{n}\\log{(1\/\\rho)}})$ bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of $O(1)$ for graphs that exclude any fixed minor.<\/jats:p>","DOI":"10.1137\/120873996","type":"journal-article","created":{"date-parts":[[2014,4,29]],"date-time":"2014-04-29T12:51:46Z","timestamp":1398775906000},"page":"872-904","source":"Crossref","is-referenced-by-count":22,"title":["Min-Max Graph Partitioning and Small Set Expansion"],"prefix":"10.1137","volume":"43","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uriel","family":"Feige","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantin","family":"Makarychev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Seffi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,4,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793525309000096"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1350-7"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/1400181.1400204"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"atypb5","first-page":"267","author":"Bansal N.","year":"2011","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Probabilistic approximation of metric spaces and its algorithmic applications\n                      , in 37th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1996, pp. 184-193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Charikar, T. Leighton, S. Li, and A. Moitra,\n                      Vertex sparsifiers and abstract rounding algorithms\n                      , in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 265-274.","DOI":"10.1109\/FOCS.2010.32"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"J. Cheeger, B. Kleiner, and A. Naor,\n                      A $(\\log n)^{\\Omega(1)}$ integrality gap for the sparsest cut SDP\n                      , in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 555-564.","DOI":"10.1109\/FOCS.2009.47"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"E. Chlamtac, K. Makarychev, and Y. Makarychev,\n                      How to play unique games using embeddings\n                      , in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2006, pp. 687-696.","DOI":"10.1109\/FOCS.2006.36"},{"key":"atypb11","first-page":"783","author":"Chowdhury N. M. M. K.","year":"2009","journal-title":"NJ"},{"key":"atypb12","first-page":"152","author":"Englert M.","year":"2010","journal-title":"Berlin"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796308217"},{"key":"atypb14","first-page":"871","author":"Fakcharoenphol J.","year":"2003","journal-title":"Berlin"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00394-3"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krauthgamer, and J. R. Lee,\n                      Bounded geometries, fractals, and low-distortion embeddings\n                      , in 44th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2003, pp. 534-543.","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00143-2"},{"key":"atypb19","first-page":"682","author":"Klein P.","year":"1993","journal-title":"New York"},{"key":"atypb20","first-page":"942","author":"Krauthgamer R.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a005"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. R. Lee and A. Naor,\n                      $L_p$ metrics on the Heisenberg group and the Goemans-Linial conjecture\n                      , in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2006, pp. 99-108.","DOI":"10.1109\/FOCS.2006.47"},{"key":"atypb23","first-page":"193","author":"Lee J. R.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb24","first-page":"47","author":"Leighton T.","year":"2010","journal-title":"New York"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"K. Makarychev and Y. Makarychev,\n                      Metric extension operators, vertex sparsifiers and Lipschitz extendability\n                      , in in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 255-264.","DOI":"10.1109\/FOCS.2010.31"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"A. Moitra,\n                      Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size\n                      , in in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 3-12.","DOI":"10.1109\/FOCS.2009.28"},{"key":"atypb29","first-page":"255","author":"R\u00e4cke H.","year":"2008","journal-title":"New York"},{"key":"atypb30","first-page":"631","author":"Raghavendra P.","year":"2010","journal-title":"New York"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"P. Raghavendra, D. Steurer, and M. Tulsiani,\n                      Reductions between expansion problems\n                      , in IEEE Conference on Computational Complexity, 2012, IEEE Computer Society, New York, pp. 64-73.","DOI":"10.1109\/CCC.2012.43"},{"key":"atypb32","first-page":"755","author":"Raghavendra P.","year":"2010","journal-title":"New York"},{"key":"atypb33","first-page":"300","author":"Rao S.","year":"1999","journal-title":"New York"},{"key":"atypb34","first-page":"207","author":"Svitkina Z.","year":"2004","journal-title":"Berlin"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/1355734.1355737"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"Y. Zhu and M. H. Ammar,\n                      Algorithms for assigning substrate network resources to virtual network components\n                      , in INFOCOM, IEEE, Piscataway, NJ, 2006.","DOI":"10.1109\/INFOCOM.2006.322"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120873996","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:38Z","timestamp":1787338298000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120873996"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120873996"],"URL":"https:\/\/doi.org\/10.1137\/120873996","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}