Approximation algorithms for the partition set cover problem with penalties

In this paper, we consider the partition set cover problem with penalties. In this problem, we have a universe U, a partition $$\mathscr {P}=\{P_{1},\ldots ,P_{r}\}$$ P = { P 1 , … , P r } of U, and a collection $$\mathscr {S}=\{S_{1},\ldots ,S_{m}\}$$ S = { S 1 , … , S m } of nonempty subsets of U satisfying $$\bigcup _{S_i\in \mathscr {S}} S_i=U$$ ⋃ S i ∈ S S i = U . In addition, each $$P_t$$ P t $$(t\in [r])$$ ( t ∈ [ r ] ) is associated with a covering requirement $$k_t$$ k t as well as a penalty $$\pi _t$$ π t , and each $$S_i$$ S i $$(i\in [m])$$ ( i ∈ [ m ] ) is associated with a cost. A class $$P_t$$ P t attains its covering requirement by a subcollection $$\mathscr {A}$$ A of $$\mathscr {S}$$ S if at least $$k_t$$ k t elements in $$P_t$$ P t are contained in $$\bigcup _{S_i\in \mathscr {A}} S_i$$ ⋃ S i ∈ A S i . Each $$P_t$$ P t is either attaining its covering requirement or paid with its penalty. The objective is to find a subcollection $$\mathscr {A}$$ A of $$\mathscr {S}$$ S such that the sum of the cost of $$\mathscr {A}$$ A and the penalties of classes not attaining covering requirements by $$\mathscr {A}$$ A is minimized. We present two approximation algorithms for this problem. The first is based on the LP-rounding technique with approximation ratio $$K+O(\beta +\ln r)$$ K + O ( β + ln r ) , where $$K=\max _{t\in [r]}k_t$$ K = max t ∈ [ r ] k t , and $$\beta $$ β denotes the approximation guarantee for a related set cover instance obtained by rounding the standard LP. The second is based on the primal-dual method with approximation ratio lf, where $$f=\max _{e\in U}|\{S_i\in \mathscr {S}\mid e\in S_i\}|$$ f = max e ∈ U | { S i ∈ S ∣ e ∈ S i } | and $$l=\max _{t\in [r]}|P_t|$$ l = max t ∈ [ r ] | P t | .