Skip to main content
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

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

Published Web Location
No data is associated with this publication.

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.

Item not freely available? Link broken?
Report a problem accessing this item