Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets ( S 2^E ), a total covering ratio q, each set (S S ) is associated with a cost (c_S ), each element (e E ) is associated with a covering requirement (r_e ), the goal is to find a minimum cost sub-collection ( S ' S ) to fully cover at least q|E| elements, where element e is fully covered if it belongs to at least (r_e ) sets of ( S ' ). Denote by (r_ = r_e:e E ) the maximum covering requirement. We present an ((O (r_ ^2n(1+ ( 1 )+ 1-q q )),1- ) )-bicriteria approximation algorithm, that is, the output of our algorithm has cost (O(r_ ^2 n(1+ ( 1 )+ 1-q q )) ) times of the optimal value while the number of fully covered elements is at least ((1- )q|E| ).
From the above related work, it can be seen that both PSC and SMC admit performance ratios matching those best ratios for the classic set cover problem. However, combining partial set cover with set multi-cover has enormously increased the difficulty of studies. Ran @cite_6 were the first to study approximation algorithms for PSMC, using greedy strategy and dual-fitting analysis. However, their ratio is meaningful only when the covering percentage @math is very close to @math . In paper @cite_20 , the authors presented a simple greedy algorithm achieving performance ratio @math . They also presented a local ratio algorithm, which reveals a what they called shock wave'' phenomenon: their performance ratio is @math for both PSC and SMC , however, when @math is smaller than 1 by a very small constant, the ratio jumps abruptly to @math . In our recent paper @cite_21 , we proved that PSMC cannot have a better than polynomial performance ratio by a reduction from the well-known densest @math -subgraph problem .
@cite_20 @cite_21 @cite_6
2509865736 2901780026 2291861235
In this paper, we study the minimum partial set multi-cover problem (PSMC). Given an element set E, a collection of subsets ( S 2^E ), a cost (c_S ) on each set (S S ), a covering requirement (r_e ) for each element (e E ), and an integer k, the PSMC problem is to find a sub-collection ( F S ) to fully cover at least k elements such that the cost of ( F ) is as small as possible, where element e is fully covered by ( F ) if it belongs to at least (r_e ) sets of ( F ). This paper presents an approximation algorithm using local ratio method achieving performance ratio ( k ( 1 f-r_ + r_ r_ ) , 1 + f r_ + 1 r_ - 1 r_ -1, 1 ), where ( ) is the size of a maximum set, f is the maximum number of sets containing a common element, ( ) is the minimum percentage of elements required to be fully covered during iterations of the algorithm, and (r_ ) and (r_ ) are the maximum and the minimum covering requirement, respectively. In particular, when (r_ ) is a constant, the first term can be omitted. Notice that our ratio coincides with the classic ratio f for both the set multi-cover problem (in which case (k=|E| )) and the partial set single-cover problem (in which case (r_ =1 )). However, when (k 1 ), the ratio might be as large as ( (n) ). This result shows an interesting “shock wave like” feature of approximating PSMC. The purpose of this paper is trying to arouse some interest in such a feature and attract more work on this challenging problem. In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets ( S 2^E ), a cost (w_S ) on each set (S S ), a covering requirement (r_e ) for each element (e E ), and an integer k, the goal is to find a sub-collection ( F S ) to fully cover at least k elements such that the cost of ( F ) is as small as possible, where element e is fully covered by ( F ) if it belongs to at least (r_e ) sets of ( 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^ 1 2( n)^c ) ) under the ETH assumption. A primal dual algorithm for MinPSMC is presented with a guaranteed performance ratio (O( n ) ) when (r_ ) and f are constants, where (r_ = _ e E r_e ) is the maximum covering requirement and f is the maximum frequency of elements (that is the maximum number of sets containing a common element). We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure. Influence problem is one of the central problems in the study of online social networks, the goal of which is to influence all nodes with the minimum number of seeds. However, in the real world, it might be too expensive to influence all nodes. In many cases, it is satisfactory to influence nodes only up to some percent p. In this paper, we study the minimum partial positive influence dominating set (MPPIDS) problem. In fact, we presented an approximation algorithm for a more general problem called minimum partial set multicover problem. As a consequence, the MPPIDS problem admits an approximation with performance ratio @math źH(Δ), where @math H(·) is the Harmonic number, @math ź=1 (1-(1-p)ź),źźΔ2 ź, and @math Δ,ź are the maximum degree and the minimum degree of the graph, respectively. For power-law graphs, we show that our algorithm has a constant performance ratio.