We study graph partitioning problems on graphs with edge capacities and ver
tex weights. The problems of b-balanced cuts and k-balanced partitions are
unified into a new problem called minimum capacity rho-separators. A rho-se
parator is a subset of edges whose removal partitions the vertex set into c
onnected components such that the sum of the vertex weights in each compone
nt is at most rho times the weight of the graph. We present a new and simpl
e O(log n)-approximation algorithm for minimum capacity rho-separators whic
h is based on spreading metrics yielding an O(log n)-approximation algorith
m both for b-balanced cuts and k-balanced partitions. In particular, this r
esult improves the previous best known approximation factor for k-balanced
partitions in undirected graphs by a factor of O(log k). We enhance these r
esults by presenting a version of the algorithm that obtains an O(log OPT)-
approximation factor. The algorithm is based on a technique called spreadin
g metrics that enables us to formulate directly the minimum capacity rho-se
parator problem as an integer program. We also introduce a generalization c
alled the simultaneous separator problem, where the goal is to find a minim
um capacity subset of edges that separates a given collection of subsets si
multaneously. We extend our results to directed graphs for values of rho gr
eater than or equal to 1/2. We conclude with an efficient algorithm for com
puting an optimal spreading metric for rho-separators. This yields more eff
icient algorithms for computing b-balanced cuts than were previously known.