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 - <p style="text-align: justify;">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.</p>