1
$\begingroup$

From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if we find a lower bound $L_B$ on $OPT$ then $$L_B \leq OPT$$

and if we correctly analyze the following $$SOL_G \leq f . L_B$$ Then we can conclude that $$SOL_G \leq f. OPT$$ where $f$ is the approximation factor of our greedy solution.

Vijay Vazirani in his book approximation algorithm on page 16 proposed the Greedy Set cover and his analysis of the lower bound on the optimum (Lemma 2.3). I have problem with understanding this Lemma:

From his convention at the beginning of the book, $OPT$ stands for the optimum solution of the problem instance (not the optimum that is obtained by the approximation algorithm).

At the beginning of the Lemma he says

In any iteration, the leftover sets of the optimal solution can cover the remaining elements at a cost of at most OPT

It is clear because $\sum_{e \in U} price(e) = OPT$. (The price assignment is based on the selection of the sets)

In the next sentence he says

Therefore, among these sets, there must be one having cost-effectiveness of at most $OPT/|\bar{C}|$ where $\bar{C} = U - C$

and $C$ is the current list of selected sets.

I can't understand, why is it true? $OPT$ is the optimum of problem instance not the algorithm. Because in the algorithm the price of each set is distributed among its elements, it seems he uses this fact but $OPT$ is not about the algorithm! it is the optimum of problem instance

Thanks.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

Let's assume for simplicity that $C = \emptyset$; I'll let you work out the general case. Note that there are at most $|U|$ sets in OPT. Let $OPT = \{O_1,\ldots,O_m\}$, where $m \leq |U|$. We have $$ \sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i \setminus (O_1 \cup \cdots \cup O_{i-1})|}{|U|} \leq \sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i|}{|U|} = \frac{OPT}{|U|}. $$ On the left-hand side we have a weighted average of the quantities $c(O_i)/|O_i|$, so one of them must be at most $OPT/|U|$. The greedy algorithm selects a set $S$ with $c(S)/|S|$ minimal, so in particular $$ \frac{c(S)}{|S|} \leq \min\left(\frac{c(O_1)}{|O_1|},\ldots,\frac{c(O_m)}{|O_m|}\right) \leq \frac{OPT}{|U|}. $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hi, Thank you for your reply. For $i=1$ the weighted average is not defined, right? there is no $O_0$. The weighted average is some thing like $$\dfrac{\sum w_i n_i}{\sum n_i}$$ I didn't fully understand the left hand side (weighted average) $\endgroup$
    – M a m a D
    Feb 1, 2016 at 16:22
  • $\begingroup$ For $i = 1$ it's just $|O_1|$. The weighted average here is $\sum_{i=1}^m w_i p_i$, where $\sum_{i=1}^m p_i = 1$. $\endgroup$
    – Yuval Filmus
    Feb 1, 2016 at 16:28
  • $\begingroup$ The greedy algorithm selects $S$ with $\dfrac{c(S)}{|S-C|}$ minimal (where $C$ is the current list of sets, in other word the currently covered elements of $U$) not a set with minimum $\dfrac{c(S)}{|S|}$. So by this fact, how the following can be true? $$ \frac{c(S)}{|S|} \leq \min\left(\frac{c(O_1)}{|O_1|},\ldots,\frac{c(O_m)}{|O_m|}\right). $$ $\endgroup$
    – M a m a D
    Feb 1, 2016 at 16:36
  • $\begingroup$ I only consider the case $C = \emptyset$. Once you understand this case, it's not difficult to generalize to arbitrary $C$. $\endgroup$
    – Yuval Filmus
    Feb 1, 2016 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.