neal young / Khuller94Primal

  • publication/Khuller94Primal.png The paper describes a simple deterministic parallel/distributed \((2+\epsilon)\)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing). This paper was one of the first to use the primal-dual method for approximation in the distributed setting. This result was strengthened in `` Distributed and parallel algorithms for weighted vertex cover and other covering problems.''
    Journal version of [1993].

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.