1
$\begingroup$

I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total sum of intra-partition edges (sum of edge weights within partitions themselves). I'm aware that it's np-hard, but do such algorithms exist, even approximations?

$\endgroup$
1
  • 1
    $\begingroup$ Given graph with edge weights in $\{0,\infty\}$, the problem of determining whether there exists a 3-partition of the vertices that has cost zero by your metric (that is, uses only zero-weight edges within each cluster) is equivalent to the 3-COLOR problem (on the corresponding graph containing only the infinite-weight edges). So this problem cannot be approximated at all in polynomial time unless P=NP. $\endgroup$
    – Neal Young
    Nov 21 at 14:26

1 Answer 1

0
$\begingroup$

One such problem is maximum agreement correlation clustering as discussed by Swamy (2004). For general weighted graphs, this problem is APX-hard (Charikar, Guruswami and Wirth 2005). For unweighted complete graphs, there exists a PTAS (Bansal, Blum and Chawla 2004).

$\endgroup$
0

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.