How do I prove the correctness of this algorithm?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What are your thoughts? Have you made any progress on this problem? Do you have any ideas at all? $\endgroup$ – Yuval Filmus Oct 21 '20 at 14:05
-
$\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W.♦ Oct 22 '20 at 3:53
Add a comment
|
$\begingroup$
$\endgroup$
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 $
