Improved approximation algorithms for MAXk-CUT and MAX BISECTION |
| |
Authors: | A Frieze M Jerrum |
| |
Affiliation: | (1) Department of Mathematics, Carnegie Mellon University, 15213 Pittsburgh, PA, USA;(2) Department of Computer Science, University of Edinburgh, The King’s Buildings, EH9 3JZ Edinburgh, Scotland |
| |
Abstract: | Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning
the vertices of a weighted graph intok 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.
The first author was supported in part by NSF Grant CCR-9225008. The work described here was undertaken while the second author
was visiting Carnegie Mellon University; at that time he was a Nuffield Science Research Fellow, and was supported in part
by Grant GR/F 90363 of the UK Science and Engineering Research Council, and Esprit Working Group 7097 “RAND”. |
| |
Keywords: | Approximation algorithms Combinatorial optimization Graph connectivity Randomized algorithms Semidefinite programming |
本文献已被 SpringerLink 等数据库收录! |
|