full
search.png

Search

close.png

Cancel

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

Da-Chuan Xu & Ji-Ye Han

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

Published online: 2003-06

Preview Full PDF 2864 25257

Cited by

google scholar semantic scholar
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, Approximation ratio.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-21-357, author = {Xu , Da-Chuan and Han , Ji-Ye}, 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 - Xu , Da-Chuan AU - Han , Ji-Ye 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, Max-Bisection problem, Semidefinite programming, Approximation ratio. 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.

Xu , Da-Chuan and Han , Ji-Ye. (2003). Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation. Journal of Computational Mathematics. 21 (3). 357-366. doi:
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard