𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of the weighted set covering problem

✍ Scribed by Jian Yang; Joseph Y-T. Leung

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
122 KB
Volume
52
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

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. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005

📜 SIMILAR VOLUMES

A generalization of the Oberwolfach prob
A generalization of the Oberwolfach problem
✍ S. I. El-Zanati; S. K. Tipnis; C. Vanden Eynden 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __n__ > 1 be an integer and let __a__~2~,__a__~3~,…,__a__~__n__~ be nonnegative integers such that $\sum\_{i=2}^{n} a\_i=2^{n-1} - 1$. Then $K\_{2^n}$ can be factored into $a\_2 C\_{2^2}$‐factors, $a\_3 C\_{2^3}$‐factors,…,$a\_n C\_{2^n}$‐factors, plus a 1‐factor. © 2002 Wiley Perio

A weighted generalization of Tur�n's the
A weighted generalization of Tur�n's theorem
✍ Bondy, J. A.; Tuza, Zs. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 2 views

We obtain a generalization of Turán's theorem for graphs whose edges are assigned integer weights. We also characterize the extremal graphs in certain cases.

The multi-integer set cover and the faci
The multi-integer set cover and the facility terminal cover problem
✍ Dorit S. Hochbaum; Asaf Levin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

## Abstract The facility terminal cover problem is a generalization of the vertex cover problem. The problem is to “cover” the edges of an undirected graph __G__ = (__V__,__E__) where each edge __e__ is associated with a non‐negative demand __d__~__e__~. An edge __e__ = __u__,__v__ is covered if at

Using Homogeneous Weights for Approximat
Using Homogeneous Weights for Approximating the Partial Cover Problem
✍ Reuven Bar-Yehuda 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 88 KB

In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold ˆ , our objective is