# Correctness proof of a greedy approximation algorithm

How do I prove the correctness of this algorithm?

• What are your thoughts? Have you made any progress on this problem? Do you have any ideas at all? – Yuval Filmus Oct 21 '20 at 14:05
• cs.stackexchange.com/q/59964/755 – D.W. Oct 22 '20 at 3:53

Desicion of Algorithms : $$T_{1},T_{2},....,T_{i}$$ , cost $$C = C_{1},C_2,....,C_i$$

$$\frac{Algo}{Opt} = \frac{C_1 + C_2 + ... + C_i}{(C_1/n_1)*n}$$

and $$4C_1 \geq C_k ,\forall 1 \leq k \leq m$$

$$\implies \frac{C_1 + C_2 + ... + C_i}{(C_1/n_1) * n} \leq \frac{4iC_1}{(C_1/n_1)*n} = \frac{4in_1}{n}$$

consider $$\frac{C_1}{n_1} \leq \frac{C_k}{n_k} \leq \frac{4C_1}{n_k} \implies n_k \leq 4n_1$$

$$\implies n_1 + n_2 + ... + n_{i-1} \leq n \implies 4(i - 1)n_1 \leq n \implies \frac{4in1}{n} \leq \frac{4n_1 + n}{n}$$

$$\frac{Algo}{Opt} \leq \frac{4in_1}{n} \leq \frac{4n_1 + n}{n} \leq \frac{4n_1 + n_1}{n_1} \leq 5$$