The Design And Analysis Of Exact Algorithms And Approximation Algorithms For The Rooted Budgeted Cycle Cover Problem

The Cycle Cover problem is a classic combinatorial optimization problem in the fields of vehicle routing and wireless sensor networks.At the algorithmic level,solving the Cycle Cover problem has significant reference value for solving other cover problems,such as the Tree Cover problem,the Path Cover problem,and the Star Cover problem.At the application level,the Cycle Cover problem can be applied in wireless sensor networks to solve tasks such as recharging wireless sensors and collecting data.The Rooted Budgeted Cycle Cover(RBCC)problem is a variant of the Cycle Cover Problem,in which the objective is to use cycles to cover(visit)all vertices in graph,with the constraint that each cycle’s length can not exceed a given budget B,and each cycle must pass through a given root vertex(called depot).According to the number of depots allowed,the RBCC problem can be divided into two categories,i.e.,the Single Depot Budget Cycle Cover(SDBCC)problem and the Multi-depot Budgeted Cycle Cover(MDBCC)problem.The RBCC problem is a NP-hard problem,which means that there is no polynomial-time algorithm to find its optimal solution unless P=NP.Currently,research on RBCC problem lacks efficient algorithms for finding exact solutions(optimal solutions)and approximate solutions(good feasible solutions).In this paper,we study the RBCC problem from the aspects of both exact algorithm and approximation algorithm.First of all,we design a dynamic programming algorithm for the RBCC problem whose time complexity is O*(3n).The algorithm can be divided into two stages.In the first stage,as the preprocessing step,we use the dynamic programming technique to obtain the optimal TSP tours for all subsets of vertices containing the depot.Then in the second stage,we use the dynamic programming technique to obtain the optimal solution for the RBCC problem.Our dynamic programming algorithm is the first nontrivial exact algorithm for the RBCC problem,and has the smallest time complexity in the known exact algorithms for the RBCC problem.The exact algorithm can quickly find the optimal solution for the RBCC problem when the problem size is small.But when the problem size becomes larger,there is a phenomenon called "combinatorial explosion" that makes the RBCC problem unsolvable.For larger scale problems,people generally use approximation algorithms to solve them.Therefore,we design an approximation algorithm for the SDBCC problem and the MDBCC problem respectively,and provide the proofs for the approximation ratios.For the SDBCC problem,we design an O(logB/μ)-approximation algorithm,where μ is the minimum difference of any two different distances between the vertices in V and the depots in D.Our technique to achieve this result is by classifying the vertices to many consecutive layers.For each layer,we use several path segments to cover the vertices in this layer.Each path segment is converted into a cycle by connecting its two endpoints to the depot.This result improves the known bicriteria approximation algorithm for the SDBCC problem.For the MDBCC problem,we design an O(log n)-approximation algorithm,where n is the number of vertices.The algorithm uses a greedy strategy to repeatedly cover some vertices with a length-limited cycle until all the vertices in the set V\D are covered.To the best of our knowledge,our O(log n)-approximation algorithm is the first nontrivial approximation for the MDBCC problem.Finally,we test the performance of the two approximation algorithms on randomly generated instances.The experimental results show that the two algorithms both have good performance in practice.The solution(i.e.,the number of cycles)obtained by the approximation algorithms on the test instances is far less than the theoretical upper bound of the solution of the algorithms,and the solutions obtained by the approximation algorithm for the MDBCC problem are very close to the optimal solutions.Therefore,the two approximation algorithms proposed in this paper can be used as subroutines with theoretical performance guarantees to solve the RBCC problem in practice.