𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Preserving approximation in the Min—Weighted Set Cover Problem

✍ Scribed by Giorgio Gambosi; Marco Protasi; Maurizio Talamo

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
616 KB
Volume
73
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we prove that the approximate solutions to the Min-Weighted Set Cover Problem provided by Chvatal's algorithm are combinatorially k-stable with respect to element insertions.

Intuitively speaking, we define an approximate solution as combinatorially k-stable with respect to an update operation if its approximation ratio remains the same even if the problem instance is modified by any sequence of at most k such operations. This implies that, if no more than k updates are performed, the approximation ratio is preserved at no computational cost.

In particular, we show that any solution returned by Chvatal's algorithm is combinatorially O(log m)-stable with respect to insertions, where m is the number of items in the instance. Hence, since the approximation ratio O(log m) is optimal, the best level of approximability is preserved.

📜 SIMILAR VOLUMES

A generalization of the weighted set cov
A generalization of the weighted set covering problem
✍ Jian Yang; Joseph Y-T. Leung 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## 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,

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

Approximation results for min-max path c
Approximation results for min-max path cover problems in vehicle routing
✍ Zhou Xu; Liang Xu; Chung-Lun Li 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 410 KB

## Abstract This article studies a min‐max path cover problem, which is to determine a set of paths for __k__ capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when