A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers

✍ Scribed by S. Khuller; U. Vishkin; N. Young

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 413 KB
• Volume: 17
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1994.1036

✦ Synopsis

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-it uses only "local" information at each step, yet is deterministic. (Generally, such algorithms have required randomization.) The result demonstrates that linear-programming primal-dual approximation techniques can lead to fast, efficient parallel algorithms. The presentation does not assume knowledge of such techniques. 1994 Academic Press. Inc.