.png){kind=icon}
.png){kind=icon}
Return
Parallel approximation for partial set cover
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2021.126358.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In a minimum partial set cover problem (MinPSC), given a ground set E with n elements, a collection S of subsets of E with vertical bar S vertical bar = m, a cost function c : S -> R+, and an integer k <= n, the goal of MinPSC is to find a minimum cost sub-collection of S that covers at least k elements of E. In this paper, we design a parallel algorithm for MinPSC which yields a solution with approximation ratio at most f/1-2 epsilon in O(1/epsilon log mn/epsilon) rounds, where f is the maximum number of sets containing a common element, and 0 < epsilon < 1/2 is a constant. We also design a parallel algorithm for a special MinPSC problem, the minimum power partial cover problem (MinPPC), which achieves approximation ratio at most (3+2 epsilon)(alpha)/1-2 epsilon in O(1/epsilon log mn/epsilon log(2) m) rounds, where alpha >= 1 is the attenuation factor of power. (C) 2021 Elsevier Inc. All rights reserved.
Keywords:
Minimum partial set cover
Minimum power partial cover
Parallel algorithm
Approximation ratio
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W