## 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