Can I read Uniform unweighted set cover: The power of non-oblivious local search on EtoBox?

Uniform unweighted set cover: The power of non-oblivious local search by Asaf Levin; Uri Yovel is a Computer Science article available to read on EtoBox.

What is Uniform unweighted set cover: The power of non-oblivious local search about?

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 H k , where H k 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) =

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

Author

Asaf Levin; Uri Yovel

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2011

Language

EN

Field

Computer Science (Physical Sciences)