full
search.png

Search

close.png

Cancel

arrow
Volume 42, Issue 5
A Simple Iterative Algorithm for Maxcut

Sihong Shao, Dong Zhang & Weixi Zhang

DOI: 10.4208/jcm.2303-m2021-0309

J. Comp. Math., 42 (2024), pp. 1277-1304.

Published online: 2024-07

Preview Purchase PDF 39 357

Cited by

google scholar semantic scholar
Export citation
  • Abstract

We propose a simple iterative (SI) algorithm for the maxcut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in [Ann. Oper. Res., 248 (2017), 365–403] are at least 0.986 and can be further improved to at least 0.997 by a preliminary attempt to break out of local optima.

  • Keywords

Maxcut, Iterative algorithm, Exact solution, Subgradient selection, Fractional programming.

  • AMS Subject Headings

90C27, 05C85, 65K10, 90C26, 90C32

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-42-1277, author = {Shao , SihongZhang , Dong and Zhang , Weixi}, title = {A Simple Iterative Algorithm for Maxcut}, journal = {Journal of Computational Mathematics}, year = {2024}, volume = {42}, number = {5}, pages = {1277--1304}, abstract = {

We propose a simple iterative (SI) algorithm for the maxcut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in [Ann. Oper. Res., 248 (2017), 365–403] are at least 0.986 and can be further improved to at least 0.997 by a preliminary attempt to break out of local optima.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2303-m2021-0309}, url = {http://global-sci.org/intro/article_detail/jcm/23278.html} }
TY - JOUR T1 - A Simple Iterative Algorithm for Maxcut AU - Shao , Sihong AU - Zhang , Dong AU - Zhang , Weixi JO - Journal of Computational Mathematics VL - 5 SP - 1277 EP - 1304 PY - 2024 DA - 2024/07 SN - 42 DO - http://doi.org/10.4208/jcm.2303-m2021-0309 UR - https://global-sci.org/intro/article_detail/jcm/23278.html KW - Maxcut, Iterative algorithm, Exact solution, Subgradient selection, Fractional programming. AB -

We propose a simple iterative (SI) algorithm for the maxcut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in [Ann. Oper. Res., 248 (2017), 365–403] are at least 0.986 and can be further improved to at least 0.997 by a preliminary attempt to break out of local optima.

Sihong Shao, Dong Zhang & Weixi Zhang. (2024). A Simple Iterative Algorithm for Maxcut. Journal of Computational Mathematics. 42 (5). 1277-1304. doi:10.4208/jcm.2303-m2021-0309
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard