A primal-dual parallel approximation technique applied to weighted set and vertex covers

Samir Khuller, Uzi Vishkin, Neal Young

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)280-289
Number of pages10
JournalJournal of Algorithms
Volume17
Issue number2
DOIs
StatePublished - Sep 1994

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A primal-dual parallel approximation technique applied to weighted set and vertex covers'. Together they form a unique fingerprint.

Cite this