3
$\begingroup$

An interesting problem has come up in my work, and I haven't quite been able to find references to it so I thought I'd ask here.

Suppose we have some complete, weighted graph with vertex set $V$. Is there an algorithm to partition $V$ into $V_1, V_2$ such that the sum of the edge weights going between the two sets is maximized (or some approximation thereof)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is the weighted MAX CUT problem, and it is NP-hard to compute exactly. Note that the case of $\{0,1\}$-weights corresponds to computing a MAX CUT in an arbitrary graph. This later problem has a beautiful polynomial-time approximation algorithm via semidefinite programming due to Goemans and Williamson, with an approximation ratio of $\alpha \approx 0.878$. Under the Unique Games Conjecture, this ratio is best possible.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah, of course. Thank you! $\endgroup$
    – bumbling-tadpole
    Commented May 28, 2019 at 13:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .