New Approximation Algorithms for the Rooted Budgeted Cycle Cover Problem

Abstract

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 \setminus D$ (containing nodes), and a budget $B \ge 0$, the rooted BCC problem asks to find a minimum number of cycles such that each cycle has length at most B and must contain a depot in D, and that these cycles collectively cover all the nodes in $V \setminus 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(\log \frac{B}{\mu })$-approximation algorithm, where $\mu$ is the minimum distance. For the rooted BCC problem with multiple depots, we give an $O(\log n)$-approximation algorithm, where n is the number of vertices. Experiments show that our algorithms have good performance in practice.