论文标题
使用树分解的启发式算法，以解决最大的快乐顶点问题
A heuristic algorithm using tree decompositions for the maximum happy vertices problem
论文作者
论文摘要
我们提出了一种使用树分解的新方法来开发启发式算法。传统上，这种算法通过动态编程方法构建了给定问题实例的最佳解决方案。我们通过引入一个参数$ W $来修改此过程，该参数$ w $决定要考虑的动态编程状态数量。我们放弃了精确的保证，支持较短的运行时间。但是，如果$ w $足够大，以至于考虑所有有效状态，我们的启发式算法证明了构造解决方案的最佳性。特别是，我们使用这种方法实现了一种启发式算法，以解决最大的快乐顶点问题。与有界树宽的图形相比，我们的算法更有效地构建了最佳解决方案。此外，我们的算法构建了比最先进的启发式算法的质量解决方案，贪婪-MHV和增长-MHV对于最初至少40％的顶点是彩色的，以较大的运行时间为代价。
We propose a new methodology to develop heuristic algorithms using tree decompositions. Traditionally, such algorithms construct an optimal solution of the given problem instance through a dynamic programming approach. We modify this procedure by introducing a parameter $W$ that dictates the number of dynamic programming states to consider. We drop the exactness guarantee in favour of a shorter running time. However, if $W$ is large enough such that all valid states are considered, our heuristic algorithm proves optimality of the constructed solution. In particular, we implement a heuristic algorithm for the Maximum Happy Vertices problem using this approach. Our algorithm more efficiently constructs optimal solutions compared to the exact algorithm for graphs of bounded treewidth. Furthermore, our algorithm constructs higher quality solutions than state-of-the-art heuristic algorithms Greedy-MHV and Growth-MHV for instances of which at least 40\% of the vertices are initially coloured, at the cost of a larger running time.
