Problem definition: Given a universe $U$ of $n$ elements, a collection of subsets of $U$, $S = \{S_1,..., S_k\}$, and a cost function $c: S \to Q^{+}$. Find a minimum cost subcollection of $S$ that covers all elements of $U$.

The provided algorithm (Approximation algorithms - Vijay V. Vazirani)

enter image description here

Part of the proof where I have trouble to understand enter image description here

My question

I have a difficult time to understand the last in equality, if $|\bar{C}| \leq n - k + 1$, why does $\cfrac{OPT}{|\bar{C}|} \leq \cfrac{OPT}{n - k + 1}$ hold?

  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Don't forget to give proper attribution to your sources! $\endgroup$
    – D.W.
    Jul 15, 2021 at 8:12

1 Answer 1


You have that $|\bar{C}| \ge n-k +1$, not $|\bar{C}| \le n-k+1$. The quantity $\frac{OPT}{|\bar{C}|}$ can only increase when we replace $\bar{C}$ with something that is at most as large. In our case we replace it with $n-k+1$.

Then: $$ \frac{OPT}{|\bar{C}|} \le \frac{OPT}{n-k+1}, $$ as desired.

  • $\begingroup$ Oh snap, I misreaded the text. Thanks. $\endgroup$ Jul 13, 2021 at 20:31

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.