Improved approximation algorithms for MAX k-CUT and MAX BISECTION
Frieze
Jerrum
10.1184/R1/6477608.v1
https://kilthub.cmu.edu/articles/journal_contribution/Improved_approximation_algorithms_for_MAX_k-CUT_and_MAX_BISECTION/6477608
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."
1994-01-01 00:00:00
Algorithms.
Polynomials.