A generalization of the weighted set covering problem

Jian Yang, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

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 [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256-278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383-390], and V. Chvatal [A greedy heuristic for the set-covering problem, Math Oper Res 4(3) (1979), 233-235] 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.

Original languageEnglish (US)
Pages (from-to)142-149
Number of pages8
JournalNaval Research Logistics
Volume52
Issue number2
DOIs
StatePublished - Mar 1 2005

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Keywords

  • Matchings
  • Networks/graphs
  • Sets
  • Stochastic model applications

Fingerprint Dive into the research topics of 'A generalization of the weighted set covering problem'. Together they form a unique fingerprint.

Cite this