Parallel approximation for partial set cover

作者：

Highlights：

• A parallel local ratio algorithm for the minimum partial set cover problem.

• A parallel algorithm for the minimum power partial cover problem.

• Run in logarithmic rounds.

• Achieve approximation ratios close to that of best known sequential algorithms.

摘要

•A parallel local ratio algorithm for the minimum partial set cover problem.•A parallel algorithm for the minimum power partial cover problem.•Run in logarithmic rounds.•Achieve approximation ratios close to that of best known sequential algorithms.

论文关键词：Minimum partial set cover,Minimum power partial cover,Parallel algorithm,Approximation ratio

论文评审过程：Received 2 March 2021, Revised 3 May 2021, Accepted 9 May 2021, Available online 26 May 2021, Version of Record 26 May 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126358