Approximation of the Quadratic Set Covering problem

Approximation of the Quadratic Set Covering problem

0.00 Avg rating0 Votes
Article ID: iaor20084159
Country: Netherlands
Volume: 4
Issue: 3/4
Start Page Number: 378
End Page Number: 386
Publication Date: Dec 2007
Journal: Discrete Optimization
Authors: ,
Keywords: sets
Abstract:

We study in this article the polynomial approximation properties of the Quadratic Set Covering problem. This problem, which arises in many applications, is a natural generalization of the usual Set Covering problem. We show that this problem is very hard to approximate in the general case, and even in classical subcases (when the size of each set or when the frequency of each element is bounded by a constant). Then we focus on the convex case and give both positive and negative approximation results. Finally, we tackle the unweighted version of this problem.

Reviews

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