neal young / Khuller94Primal
Journal of Algorithms 17(2):280-289(1994); IPCO'93The 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 .
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.