Absolute bounds on optimal cost for a class of set covering problems

We study the class of (m constraint,n variable) set covering problems which have no more thank variables represented in each constraint. Letd denote the maximum column sum in the constraint matrix, letr=m/d]?1, and letZ _g denote the cost of a greedy heuristic solution. Then we prove $$\begin{gathered} Zg \leqslant 1 + r + m - d - \left {mk \cdot MAX\left\{ {\frac{{2r}}{{2n - r - 1}},\ln \frac{n}{{n - r}}} \right\}} \right. \hfill \\ \left. { - kd \cdot MIN\left\{ {\frac{{r(r + 1)}}{{2(n - r)}},n \cdot \ln \frac{{n - 1}}{{n - r - 1}} - 1} \right\}} \right]. \hfill \\ \end{gathered} $$ This provides the firsta priori nontrivial upper bound discovered on heuristic solution cost (and thus on optimal solution cost) for the set covering problem. An example demonstrates that this bound is attainable, both for a greedy heuristic solution and for the optimal solution. Numerical examples show that this bound is substantially better than existing bounds for many problem instances. An important subclass of these problems occurs when the constraint matrix is a circulant, in which casem=n andk=d=αη] for some 0<α<1. For this subclass we prove $$\mathop {\lim }\limits_{n \to \infty } Zg/n \leqslant \frac{{\alpha ^2 }}{2}1/\alpha ]1/\alpha ].$$