Search

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 (log ⁡ B μ) -approximation algorithm, where μ 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. • A log-factor approximation algorithm for the single depot budgeted cycle cover problem. • A log-factor approximation algorithm for the multi-depot budgeted cycle cover problem. • Experiments on randomly generated instances show good performance of the algorithms. [ABSTRACT FROM AUTHOR]

k -Clustering partitions a set of n points in a metric space into at most k clusters in a way that makes the resulted clusters satisfy both the homogeneity and the separation criteria. The diameter of a cluster is the maximum distance between pairs of points in the cluster, and the split of a cluster is the minimum distance between points of the cluster and ones outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: The ratio of the minimum cluster split to the maximum cluster diameter (abbr. RSD). We study the following two optimization problems: Maximizing RSD without and with cardinality constraints, i.e., each cluster should consist of at least N points. For both problems with k ≥ 3 , it is NP-hard to achieve a factor of (1 2 + ϵ) approximation for any ϵ > 0. For k = 2 , we solve the two problems optimally; For k ≥ 3 , we present a 1 2 -approximation and a 1 4 -approximation algorithm for the two problems, respectively. [ABSTRACT FROM AUTHOR]