As a judicious correspondence to the classical maxcut, the anti-Cheeger cut has more balanced structure, but few numerical results on it have been reported so far. In this paper, we propose a continuous iterative algorithm for the anti-Cheeger cut 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 objection function values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. It can also be easily combined with the maxcut iterations for breaking out of local optima and improving the solution quality thanks to the similarity between the anti-Cheeger cut problem and the maxcut problem. Numerical experiments on G-set demonstrate the performance.
翻译:作为与经典最大截面的明智对应,反希格切面的结构更加平衡,但迄今几乎没有报告数字结果。 在本文中,我们建议通过完全使用等效连续配方,为反希格切面的问题提供连续迭代算法。 它根本不需要四舍五入,其优点是所有子问题都有明确的分析解决方案,反对函数值是单调更新的,循环点通过适当的子梯度选择,以有限的步骤向本地选择点汇合。由于反希格切面切面问题和最大截面问题之间的相似性,它也可以很容易与打破本地选择面和提高解决方案质量的峰值迭代算法相结合。 G型的数值实验证明了它的表现。