A generalization of the weighted set covering problem. (English) Zbl 1104.90011
Summary: We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect \(b\)-matching problem. In general, we may use a polynomial-time greedy heuristic similar to the one for the classical weighted set covering problem studied by D. S. Johnson [J. Comput. Syst. Sci. 9, 256–278 (1974; Zbl 0296.65036)], L. Lovasz [Discrete Math. 13, 383–390 (1975; Zbl 0323.05127)], and V. Chvatal [Math. Oper. Res. 4, 233–235 (1979; Zbl 0443.90066)] to get an approximate solution for the problem. We find a worst-case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large.
MSC:
| 90B10 | Deterministic network models in operations research |
| 91B70 | Stochastic models in economics |
| 68R10 | Graph theory (including graph drawing) in computer science |
Software:
CPLEXReferences:
| [1] | Anstee, Inform Process Lett 24 pp 153– (1987) |
| [2] | Blot, Theoret Comput Sci 147 pp 267– (1995) |
| [3] | Chvatal, Math Oper Res 4:3 pp 233– (1979) |
| [4] | Cunningham, Math Prog Study 8 pp 50– (1978) · doi:10.1007/BFb0121194 |
| [5] | Feige, J ACM 45 pp 634– (1998) |
| [6] | Gabow, Conf Proc Annu ACM Symp Theory Comput 15 pp 448– (1983) |
| [7] | ILOG CPLEX 7.0-User’s Manual, ILOG, Mountain View, California, 2000. |
| [8] | Johnson, J Comput System Sci 9 pp 256– (1974) |
| [9] | ?Reducibility among combinatorial problems,? Complexity of computer computations, and (Editors), Plenum Press, New York, 1972 pp. 85-104. · doi:10.1007/978-1-4684-2001-2_9 |
| [10] | Lovasz, Discrete Math 13 pp 383– (1975) |
| [11] | Lund, J ACM 41 pp 960– (1994) |
| [12] | and Integer and combinatorial optimization, Wiley Interscience, New York, 1988. · doi:10.1002/9781118627372 |
| [13] | Slavik, Conf Proc Annu ACM Symp Theory Comput 28 pp 435– (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
