A simple iterative algorithm for maxcut

arXiv1803.06496MaRDI QIDQ6299189FDOQ6299189

Authors: Sihong Shao, Dong Zhang, Weixi Zhang 

Publication date: 17 March 2018

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] 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.

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Fractional programming (90C32) Graph algorithms (graph-theoretic aspects) (05C85) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27)

This page was built for publication: A simple iterative algorithm for maxcut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6299189)