A primal-dual parallel approximation technique applied to weighted set and vertex covers
- Author(s): Khuller, S;
- Vishkin, U;
- Young, N
- et al.
Published Web Locationhttps://arxiv.org/abs/cs/0205037
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.