Distributed Algorithm for Set k-Cover Problem and its Worst Case Analysis

摘要

In this paper, we consider the problem of partitioning a given collection of subsets of nodes into k collections such that the average size of each collection is the largest, where the size of a collection is defined as the size of the union of the subsets contained in the collection. At first, we give an upper bound on the performance ratio of Abrams et al.'s approximation algorithm which is known to have a performance ratio of at least 1 - 1/e where e is Napier's constant. The result of numerical calculations indicates that an upper bound is 3/4 + ε for small ε > 0. Next, we design a distributed implementation of Abrams et al.'s algorithm, which is based on the idea of arbitration using a spanning tree. Our algorithm can be used for the periodical switching of active subsets in Wireless Sensor Networks.