A 6/5‐approximation algorithm for the maximum 3‐cover problem

A 6/5‐approximation algorithm for the maximum 3‐cover problem

0.00 Avg rating0 Votes
Article ID: iaor2013586
Volume: 25
Issue: 1
Start Page Number: 60
End Page Number: 77
Publication Date: Jan 2013
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: heuristics
Abstract:

In the maximum cover problem, we are given a collection of sets over a ground set of elements and a positive integer w, and we are asked to compute a collection of at most w sets whose union contains the maximum number of elements from the ground set. This is a fundamental combinatorial optimization problem with applications to resource allocation. We study the simplest APX‐hard variant of the problem where all sets are of size at most 3 and we present a 6/5‐approximation algorithm, improving the previously best known approximation guarantee. Our algorithm is based on the idea of first computing a large packing of disjoint sets of size 3 and then augmenting it by performing simple local improvements.

Reviews

Required fields are marked *. Your email address will not be published.