Multi-armed bandit for the cyclic minimum sitting arrangement problem
研究将带符号图嵌入循环宿主图的组合优化问题，提出基于多臂老虎机的算法，结合贪心随机构造与变邻域下降搜索，在超大规模集成电路设计和社会网络分析中有应用，实验表明优于现有方法。
Graphs are commonly used to represent related elements and relationships among them. Signed graphs are a special type of graphs that can represent more complex structures, such as positive or negative connections in a social network. In this work, we address a combinatorial optimization problem, known as the Cyclic Minimum Sitting Arrangement, that consists of embedding a signed input graph into a cycle host graph, trying to locate in the embedding positive connected vertices closer than negative ones. This problem is a variant of the well-known Minimum Sitting Arrangement where the host graph has the structure of a path graph. To tackle the problem, we propose an algorithm based on the Multi-Armed Bandit method that combines three greedy-randomized constructive procedures with a Variable Neighborhood Descent local search algorithm. To assess the merit of our proposal, we compare it with the state-of-the-art method. Our experiments show that our algorithm outperforms the best-known method in the literature to date, and the results are statistically significant, establishing itself as the new state of the art for the problem. • Heuristic algorithms for the Cyclic Minimum Sitting Arrangement Problem. • Greedy-randomized procedures combined with Variable Neighborhood Descent. • Hyper-heuristic based on Multi-Armed Bandit algorithm. • Applications in VLSI design and social network analysis. • Favorable empirical comparison with previous algorithms.