\input zb-basic
\input zb-ioport
\iteman{io-port 01002567}
\itemau{Frieze, A.; Jerrum, M.}
\itemti{Improved approximation algorithms for MAX $k$-cut and MAX BISECTION.}
\itemso{Algorithmica 18, No. 1, 67-81 (1997).}
\itemab
Summary: Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph into $k$ blocks so as to maximize the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite programming relaxation.
\itemrv{~}
\itemcc{}
\itemut{graph connectivity; randomized algorithms; semidefinite programming}
\itemli{doi:10.1007/BF02523688}
\end