Question

set_cover
randomize_rounding

In the set cover problem, the goal is to find a collection of subsets indexed by II that minimizes jIwj\sum_{j \in I} w_j such that

jISj=E. \left| \bigcup_{j \in I} S_j \right| = |E|.

Consider the partial cover problem, in which one finds a collection of subset indexed by II that minimizes jIwj\sum_{j \in I} w_j such that

jISj=pE. \left| \bigcup_{j \in I} S_j \right| = p|E|.

where 0<p<10 < p < 1 is some constant.

  1. Give a polynomial-time algorithm to find a solution to the partial cover problem in which the value is no more than c(p)c(p) \cdotOPT, where c(p)c(p) is a constant that depends on pp, and OPT is the value of the optimal solution to the set cover problem.
  2. Give an f(p)f(p)-approximation algorithm for the partial cover problem, such that ff is non-decreasing in pp and f(1)HEf(1) \leq H_{E}.
1

Answers

1. Consider the greedy algorithm that halts after covering pnpn elements. Let nin_i be the number of elements uncovered in the beginning of the iith iteration, then there exists a set SjS_j such that wjSjOPTniw_j \leq |S_j|\frac{OPT}{n_i}. Let S1,,StS_1, \dots, S_{t} be the sets chosen by the greedy algorithm (in that order), then the cost of the greedy solution is at most i=1t1SiOPTni+wjOPT(HnHnnp+1)OPT(lnnln(nnp)+1)=(1+ln11p)OPT\sum_{i = 1}^{t - 1} |S_i| \frac{OPT}{n_i} + w_j \leq OPT(H_n - H_{n - np} + 1) \leq OPT(\ln n - \ln(n - np) + 1) = (1 + \ln \frac{1}{1 - p})OPT.

2. Consider a greedy algorithm that in the iith iteration chooses

argminSjwjmin{SjEi,ni} \arg \min_{S_j} \frac{w_j}{\min\{|S_j \cap E_i|, n_i\}}

Where EiE_i is the set of uncovered elements at the beginning of the iith iteration and ni=np(nEi)n_i = np - (n - |E_i|).

So the optimal solution covers at least nin_i uncovered elements at the beginning of the iith iteration and thus the cost to cover the next element(s) by the greedy algorithm is at most OPTni\frac{OPT}{n_i} and the total cost is at most i=1npOPTi=Hnp\sum_{i = 1}^np \frac{OPT}{i} = H_{np}.

1
Feedback