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.