New approximation algorithms for the rooted Budgeted Cycle Cover problem

The rooted Budgeted Cycle Cover (BCC) problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space (V, w) with vertex set V consisting of two parts D (containing depots) and V \ D (containing nodes), and a budget B >= 0, the rooted BCC problem asks to find a minimum number of cycles to cover all the nodes in V \ D, satisfying that each cycle has length at most B and each cycle must contain a depot in D. In this paper, we give new approximation algorithms for the rooted BCC problem. For the rooted BCC problem with single depot, we give an O (logB mu )-approximation algorithm, where mu is the minimum difference of any two different distances between the vertices in V and the root. For the rooted BCC problem with multiple depots, we give an O (log n)-approximation algorithm, where n is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice. (c) 2022 Elsevier B.V. All rights reserved.