A Simple Iterative Algorithm for Maxcut (Journal of Computational Mathematics, 2024)
We propose a simple iterative (SI) algorithm for the maxcut problem through fully usingan equivalent continuous formulation. It does not need rounding at all and has advantagesthat 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 appropriatesubgradient selection. Numerical experiments on G-set demonstrate the performance. Inparticular, 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 least0.986 and can be further improved to at least 0.997 by a preliminary attempt to break outof local optima.