A SIMPLE ITERATIVE ALGORITHM FOR MAXCUT  

作　　者：Sihong Shao Dong Zhang Weixi Zhang 

机构地区：[1]CAPT,LMAM and School of Mathematical Sciences,Peking University,Beijing 100871,China [2]LMAM and School of Mathematical Sciences,Peking University,Beijing 100871,China

出　　处：《Journal of Computational Mathematics》2024年第5期1277-1304,共28页计算数学（英文）

基　　金：supported by the National Key R&D Program of China(Grant Nos.2020AAA0105200,2022YFA1005102);the National Natural Science Foundation of China(Grant Nos.12325112,12288101,11822102);the China Postdoctoral Science Foundation(Grant No.BX201700009).

摘　　要：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.

关 键 词：Maxcut Iterative algorithm Exact solution Subgradient selection Fractional programming 

分 类 号：O24[理学—计算数学]