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

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 Location

https://arxiv.org/abs/cs/0205037
No data is associated with this publication.
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.

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