𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A({{10}})-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem

✍ Scribed by Robert Carr; Toshihiro Fujito; Goran Konjevod; Ojas Parekh

Book ID
110301597
Publisher
Springer US
Year
2001
Tongue
English
Weight
85 KB
Volume
5
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

πŸ“œ 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,

A simple approximation algorithm for the
A simple approximation algorithm for the weighted matching problem
✍ Doratha E Drake; Stefan Hougardy πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 61 KB

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [