Home
 

Improved approximation algorithms for MAX k-CUT and MAX BISECTION

Alan Frieze and Mark Jerrum

Abstract: Polynomial-time approximation algorithms with non-trivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph into k blocks so as to maximise the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximise the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite relaxation.

LFCS report ECS-LFCS-94-292, May 1994.

Previous | Index | Next