# Trouble to understand the proof of greedy algorithm for set cover

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) Part of the proof where I have trouble to understand 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?

• 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!
– D.W.
Jul 15, 2021 at 8:12

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.