{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T08:08:35Z","timestamp":1791187715379,"version":"4.1.0"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity $\\rho$-separators. A $\\rho$-separator is a subset of edges whose removal partitions the vertex set into connected components such that the sum of the vertex weights in each component is at most $\\rho$ times the weight of the graph. We present a new and simple O(log n)-approximation algorithm for minimum capacity $\\rho$-separators which is based on spreading metrics yielding an O(log n)-approximation algorithm both for b-balanced cuts and k-balanced partitions. In particular, this result improves the previous best known approximation factor for k-balanced partitions in undirected graphs by a factor of O(log k). We enhancethese results by presenting a version of the algorithm that obtains an O(log OPT)-approximation factor. The algorithm is based on a technique called spreading metrics that enables us to formulate directly the minimum capacity $\\rho$-separator problem as an integer program. We also introduce a generalization called the simultaneous separator problem, where the goal is to find a minimum capacity subset of edges that separates a given collection of subsets simultaneously. We extend our results to directed graphs for values of $\\rho \\geq 1\/2$. We conclude with an efficient algorithm for computing an optimal spreading metric for $\\rho$-separators. This yields more efficient algorithms for computing b-balanced cuts than were previously known.<\/jats:p>","DOI":"10.1137\/s0097539796308217","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"2187-2214","source":"Crossref","is-referenced-by-count":83,"title":["Fast Approximate Graph Partitioning Algorithms"],"prefix":"10.1137","volume":"28","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00084-5"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"G. Even, J. Naor, S. Rao, and B. Schieber,\n                      Divide\u2010and\u2010conquer approximation algorithms via spreading metrics\n                      , in Proceedings 36th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, 1995, pp. 62\u201371.","DOI":"10.1109\/SFCS.1995.492463"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"R5","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.6.865"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"T. Kloks,\n                      Treewidth\n                      , Lecture Notes in Comput. Sci. 842, Springer\u2010Verlag, Berlin, Heidelberg, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0833"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1020"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"T. Leighton, F. Makedon, and S. Tragoudas,\n                      Approximation algorithms for VLSI partition problems\n                      , in Proceedings 1990 IEEE International Symposium on Circuits and Systems, (ISCAS \u25a190), New Orleans, LA, Vol. 4, IEEE Computer Society Press, Piscataway, NJ, 1990, pp. 2865\u20132868.","DOI":"10.1109\/ISCAS.1990.112608"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"T. Leighton and S. Rao,\n                      An approximate max\u2010flow min\u2010cut theorem for uniform multi\u2010commodity flow problems with applications to approximation algorithms\n                      , in Proceedings 29th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, 1988, pp. 422\u2013431; J. ACM, to appear.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"R14","unstructured":"K. Lang and S. Rao,\n                      Finding near\u2010optimal cuts: An empirical evaluation\n                      , in Proceedings 4th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Austin, TX, 1993, SIAM, Philadelphia, 1993, pp. 212\u2013221."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior\u2010Point Polynomial Algorithms in Convex Programming\n                      , SIAM Stud. Appl. Math. 13, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593255135"},{"key":"R18","unstructured":"Neal Young, Randomized rounding without solving the linear program, ACM, New York, 1995, 170\u201317895k:90040"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796308217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:40Z","timestamp":1787335960000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796308217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539796308217"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796308217","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}