Max-k-Cut by the Discrete Dynamic Convexized Method
Max-k-Cut by the Discrete Dynamic Convexized Method
复制标题
DOI：
10.1287/ijoc.1110.0492
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Wen-xing Zhu;Geng Lin;M. Ali
中科院分区：
文献类型：
--
作者：
Wen-xing Zhu;Geng Lin;M. Ali
在本文中，我们提出了一个“多启动型”算法求解最大k-割问题。我们算法的核心是我们提出的辅助函数。我们制定的max-k-cut问题作为一个明确的数学形式，这使我们能够使用一个容易实现的本地搜索。辅助函数的构造需要max-k-cut问题的局部最大化。如果在辅助函数的构造中使用所获得的最佳局部最大化，则辅助函数的局部最大化导致max-k-cut问题的更好的最大化。这被证明是一个很好的策略，以摆脱当前的局部最优，并搜索更广泛的解决方案空间。事实上，我们已经表明，无论是数值和理论上，最大化的辅助功能的局部搜索方法可以成功地逃脱以前收敛的离散局部最大值通过增加参数的值。对不同规模和密度的测试实例的计算结果表明，该算法能有效地求出max-k-cut问题的近似全局解.尽管我们已经给出了k ≥ 2的结果，但通过与一些最近的方法进行比较，我们的算法在k = 2时具有鲁棒性。一些理论结果也被提出，证明我们的算法的设计。
In this paper, we propose a “multistart-type” algorithm for solving the max-k-cut problem. Central to our algorithm is an auxiliary function we propose. We formulate the max-k-cut problem as an explicit mathematical form, which allows us to use an easy implementable local search. The construction of the auxiliary function requires a local maximizer of the max-k-cut problem. If the best local maximizer obtained is used in the construction of the auxiliary function, then the local maximization of the auxiliary function leads to a better maximizer of the max-k-cut problem. This proves to be a good strategy to escape from the current local optima and to search a broader solution space. Indeed, we have shown, both numerically and theoretically, that the maximization of the auxiliary function by the local search method can escape successfully from previously converged discrete local maximizers by taking increasing values of a parameter. Computational results on many test instances with different sizes and densities show that the proposed algorithm is efficient and stable to find approximate global solutions for the max-k-cut problems. Although we have presented results for k ≥ 2, the robustness of our algorithm is shown for k = 2 by comparisons with a number of recent methods. A number of theoretical results are also presented, which justify the design of our algorithm.