Uniform unweighted set cover: The power of non-oblivious local search

Details Uniform unweighted set cover: The power of non-oblivious local search Uniform unweighted set cover: The power of non-oblivious local search

2009-06-08

arxiv.org/abs/0906.1557v1

Computer Science

Data Structures and Algorithms

31 pages, includes figures

Scientific paper

We are given n base elements and a finite collection of subsets of them. The size of any subset varies between p to k (p < k). In addition, we assume that the input contains all possible subsets of size p. Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of (p,k) = (2,4). The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering i new elements, starting from i = k down to i = p+1. At a final step we cover the remaining base elements by the subsets of size p. We derive the exact performance guarantee of this algorithm for all values of k and p, which is less than Hk, where Hk is the k'th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted k-set cover problem (in which subset sizes are only restricted not to exceed k), and hence it serves as a benchmark for our improved algorithm. The improved algorithm for the special case of (p,k) = (2,4) is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of 1.5 + epsilon, and the local search algorithm achieves a better ratio, which is bounded by 1.458333... + epsilon.

Affiliated with

Also associated with

No associations

Rating

Uniform unweighted set cover: The power of non-oblivious local search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Uniform unweighted set cover: The power of non-oblivious local search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniform unweighted set cover: The power of non-oblivious local search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-232895