Packing-Based Approximation Algorithm for the k-Set Cover Problem

Details Packing-Based Approximation Algorithm for the k-Set Cover Problem Packing-Based Approximation Algorithm for the k-Set Cover Problem

2011-09-15

arxiv.org/abs/1109.3418v1

Computer Science

Data Structures and Algorithms

26 pages, 5 figures

Scientific paper

We present a packing-based approximation algorithm for the $k$-Set Cover problem. We introduce a new local search-based $k$-set packing heuristic, and call it Restricted $k$-Set Packing. We analyze its tight approximation ratio via a complicated combinatorial argument. Equipped with the Restricted $k$-Set Packing algorithm, our $k$-Set Cover algorithm is composed of the $k$-Set Packing heuristic \cite{schrijver} for $k\geq 7$, Restricted $k$-Set Packing for $k=6,5,4$ and the semi-local $(2,1)$-improvement \cite{furer} for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of $H_k-0.6402+\Theta(\frac{1}{k})$, where $H_k$ is the $k$-th harmonic number. For small $k$, our results are 1.8667 for $k=6$, 1.7333 for $k=5$ and 1.5208 for $k=4$. Our algorithm improves the currently best approximation ratio for the $k$-Set Cover problem of any $k\geq 4$.

Affiliated with

Also associated with

No associations

Rating

Packing-Based Approximation Algorithm for the k-Set Cover Problem 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 Packing-Based Approximation Algorithm for the k-Set Cover Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing-Based Approximation Algorithm for the k-Set Cover Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-673776