file.pdf (1.21 MB)
0/0

Improved approximation algorithms for MAX k-CUT and MAX BISECTION

Download (1.21 MB)
journal contribution
posted on 01.01.1994 by Frieze, 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."

History

Publisher Statement

All Rights Reserved

Date

01/01/1994

Exports

Exports