The multi‐integer set cover and the facility terminal cover problem
Dorit S. Hochbaum, Asaf Levin · Networks · 2008
Abstract The facility terminal cover problem is a generalization of the vertex cover problem. The problem is to “cover” the edges of an undirected graphG= (V,E) where each edgeeis associated with a non‐negative demandde. An edgee=u,vis covered if at least one of its endpoint vertices is allocated capacity of at leastde. Each vertexvis associated with a non‐negative weightwv. The goal is to allocate capacitycv≥ 0 to each vertexvso that all edges are covered and the total allocation cost,$\sum\limits_{v\in V}w_{v}c_{v}$, is minimized. A recent paper by Xu et al. [Networks 50 (2007), 118‐126], studied this problem, and presented a 2e‐ approximation algorithm for this problem forethe base of the natural logarithm. We generalize here the facility terminal cover problem to the multi‐integer set cover, and relate that problem to the set cover problem, which it generalizes, and the multi‐cover problem. We present a Δ‐approximation algorithm for the multi‐integer set cover problem, for Δ the maximum coverage. This demonstrates that even though the multi‐integer set cover problem generalizes the set cover problem, the same approximation ratio holds. In the special case of the facility terminal cover problem this yields a 2‐approximation algorithm, and with run time dominated by the sorting of the edge demands. This approximation algorithm improves considerably on the result of Xu et al. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009