Volume 21, Issue 3
Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation

Da-chuan Xu & Ji-ye Han

DOI:

J. Comp. Math., 21 (2003), pp. 357-366

Published online: 2003-06

Preview Full PDF 171 1666
Export citation
  • Abstract

Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick, The main tool used to obtain this result is semidefinite programming.

  • Keywords

Approximation algorithm Max-Bisection problem Semidefinite programming

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-21-357, author = {Da-chuan Xu and Ji-ye Han}, title = {Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation}, journal = {Journal of Computational Mathematics}, year = {2003}, volume = {21}, number = {3}, pages = {357--366}, abstract = { Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick, The main tool used to obtain this result is semidefinite programming. }, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/10264.html} }
TY - JOUR T1 - Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation AU - Da-chuan Xu & Ji-ye Han JO - Journal of Computational Mathematics VL - 3 SP - 357 EP - 366 PY - 2003 DA - 2003/06 SN - 21 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/10264.html KW - Approximation algorithm KW - Max-Bisection problem KW - Semidefinite programming AB - Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick, The main tool used to obtain this result is semidefinite programming.
Da-chuan Xu & Ji-ye Han. (1970). Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation. Journal of Computational Mathematics. 21 (3). 357-366. doi:
Copy to clipboard
The citation has been copied to your clipboard