<p>The problem is called GRAPH CONDUCTANCE, and the best algorithm is by <a href="http://doi.acm.org/10.1145/1502793.1502794">Arora et al.</a></p>

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

<p>This is a <a href="http://doi.acm.org/10.1145/1400181.1400204">more accessible version</a>, by the same authors:</p>

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

CC BY-SA 3.0
2012-04-05T17:10:50.150Z
2012-04-05T17:10:50.150Z
Yixin Cao
<p>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.</p>

<p>Any pointers are much appreciated.</p>

<ds.algorithms><reference-request><graph-theory><graph-algorithms>
Graph partitioning, balancing on within subset edge weights
PeterR
# Graph partitioning, balancing on within subset edge weights

(Asked by: username_0 on 2012-04-05)

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.

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2012-04-05. Score: 9 | Accepted answer

The problem is called GRAPH CONDUCTANCE, and the best algorithm is by [Arora et al.](http://doi.acm.org/10.1145/1502793.1502794)

> 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](http://doi.acm.org/10.1145/1400181.1400204), by the same authors:

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


---

