𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Greedy Local Improvement and Weighted Set Packing Approximation

✍ Scribed by Barun Chandra; Magnús M Halldórsson

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
134 KB
Volume
39
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the kset packing problem is to find a maximum weight subcollection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and natural local search has been shown to approximate it to within a factor of roughly k -1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. Thii is the first asymptotic improvement over the straightforward ratio of k.

📜 SIMILAR VOLUMES

A Primal-Dual Parallel Approximation Tec
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
✍ S. Khuller; U. Vishkin; N. Young 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 413 KB

We give an efficient deterministic parallel approximation algorithm for the minimum-weight vertex- and set-cover problems and their duals (edge/element packing). The algorithm is simple and suitable for distributed implementation. It fits no existing paradigm for fast, efficient parallel algorithms-

NOTE Improved Approximation Algorithms f
NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
✍ Michal Penn; Haya Shasha-Krupnik 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 126 KB

The problem of finding a minimum augmenting edge-set to make a graph k-vertex connected is considered. This problem is denoted as the minimum k-augmentation problem. For weighted graphs, the minimum k-augmentation problem is NP-complete. Our main result is an approximation algorithm with a performan