8
$\begingroup$

I'm interested in pointers to algorithms (approximation algorithms are fine) that attempt to partition a graph into two subsets such that the sum of the edge weights within each subset is (approximately) equal, and the sum of the edge weights between the two subsets is (approximately) minimal.

Any pointers are much appreciated.

$\endgroup$
9
$\begingroup$

The problem is called GRAPH CONDUCTANCE, and the best algorithm is by Arora et al.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2): (2009)

This is a more accessible version, by the same authors:

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.