A primal-dual parallel approximation technique applied to weighted set and vertex covers
- Author(s): Khuller, S
- Vishkin, U
- Young, N
- et al.
Abstract
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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.