𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating Node Connectivity Problems via Set Covers

✍ Scribed by Guy Kortsarz; Zeev Nutov

Publisher
Springer
Year
2003
Tongue
English
Weight
243 KB
Volume
37
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Preserving approximation in the Minβ€”Weig
Preserving approximation in the Minβ€”Weighted Set Cover Problem
✍ Giorgio Gambosi; Marco Protasi; Maurizio Talamo πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 616 KB

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

Computational experience with approximat
Computational experience with approximation algorithms for the set covering problem
✍ Tal Grossman; Avishai Wool πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 722 KB

The Set Covering problem (SCP) is a well known combinatorial optimization problem, which is NP-hard. We conducted a comparative study of nine different approximation algorithms for the SCP, including several greedy variants, fractional relaxations, randomized algorithms and a neural network algorith