A primal-dual algorithm for the minimum partial set multi-cover problem

Yingli Ran, Yishuo Shi, Changbing Tang and Zhao Zhang ()
Additional contact information
Yingli Ran: Zhejiang Normal University
Yishuo Shi: Institute of Information Science, Academia Sinica
Changbing Tang: Zhejiang Normal University
Zhao Zhang: Zhejiang Normal University

Journal of Combinatorial Optimization, 2020, vol. 39, issue 3, No 5, 725-746

Abstract: Abstract In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets $${\mathcal {S}} \subseteq 2^E$$S⊆2E, a cost $$w_S$$wS on each set $$S\in {\mathcal {S}}$$S∈S, a covering requirement $$r_e$$re for each element $$e\in E$$e∈E, and an integer k, the goal is to find a sub-collection $${\mathcal {F}} \subseteq {\mathcal {S}}$$F⊆S to fully cover at least k elements such that the cost of $${\mathcal {F}}$$F is as small as possible, where element e is fully covered by $${\mathcal {F}}$$F if it belongs to at least $$r_e$$re sets of $${\mathcal {F}}$$F. On the application side, the problem has its background in the seed selection problem in a social network. On the theoretical side, it is a natural combination of the minimum partial (single) set cover problem (MinPSC) and the minimum set multi-cover problem (MinSMC). Although both MinPSC and MinSMC admit good approximations whose performance ratios match those lower bounds for the classic set cover problem, previous studies show that theoretical study on MinPSMC is quite challenging. In this paper, we prove that MinPSMC cannot be approximated within factor $$O(n^\frac{1}{2(\log \log n)^c})$$O(n12(loglogn)c) for some constant c under the ETH assumption. Furthermore, assuming $$r_{\max }$$rmax is a constant, where $$r_{\max } =\max _{e\in E} r_e$$rmax=maxe∈Ere is the maximum covering requirement and f is the maximum number of sets containing a common element, we present a primal-dual algorithm for MinPSMC and show that its performance ratio is $$O(\sqrt{n})$$O(n). We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure.

Keywords: Partial set multi-cover problem; Positive influence dominating set; Densest l-subgraph problem; Primal-dual; Approximation algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00513-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:3:d:10.1007_s10878-019-00513-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00513-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().