Exact algorithms for the min-max cycle cover problem
森 袁, 开奇 陈, 江坤 李, 鹏 张 · Scientia Sinica Informationis · 2022
The min-max cycle cover problem is a generalization of the traveling salesman problem.Wireless sensor networks, UAV disaster rescue, and other fields all leverage the challenge. While approximation solutions for the min-max cycle cover issue receive a lot of attention, research on exact algorithms is sparse. Based on the combinatoric characteristics of the problem, we design the first exact algorithm for the min-max cycle cover problem using the dynamic programming strategy. We prove that the time complexity of our algorithm is $O^*(3^n)$. Our method for the min-max cycle cover problem consists of two stages. The first stage involves preprocessing the problem's input, and the second stage involves finding the best solution to the problem based on the first stage's results. Interestingly, the two stages are both based on the dynamic programming strategy. This is the main feature of our algorithm. The time complexity $O^*(3^n)$ of our algorithm is significantly better than that of the enumeration algorithm using brute-force search.