Competitive simulated annealing and Tabu Search algorithms for the max-cut problem
Competitive simulated annealing and Tabu Search algorithms for the max-cut problem
复制标题
DOI：
10.1145/1569901.1570167
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
E. Arráiz;Oswaldo Olivo
中科院分区：
文献类型：
--
作者：
E. Arráiz;Oswaldo Olivo
最大割问题是将无向赋权图的节点划分为两个子集，使得连接不同划分中两个顶点的边的权重和最大化。它在统计物理、VLSI设计等领域有着广泛的应用，并且是NP难的。我们提出了一种平衡解的多样性和质量的邻域生成方法。因此，纳入模拟退火法和禁忌搜索框架产生的结果与VNSPR和分散搜索等最先进方法报告的结果相似，在某些情况下还改进了这些结果。
The Max-Cut problem consists of partitioning the nodes of an undirected weighted graph into two subsets, such that the sum of the weights of the edges that connect two vertices in different partitions is maximized. It has applications in several fields like statistical physics, VLSI design, among others, and is known to be NP-Hard. We propose a Neighborhood generation method that balances diversity and quality of the obtained solutions. Consequently, the inclusion within Simulated Annealing and Tabu Search frameworks produces similar results to those reported by state-of-the-art methods such as VNSPR and Scatter Search, and in some cases improves them.