## DIMACS TR: 2005-09

## Approximation of the Quadratic Set Covering Problem

### Authors: Bruno Escoffier and Peter L. Hammer

**
ABSTRACT
**

We study in this article polynomial approximation 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.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-09.ps.gz

DIMACS Home Page