this is for holding javascript data
Jeremy Ting edited q3.tex
almost 10 years ago
Commit id: aa2aab99e6171a07b9e58f3b404611129d922e47
deletions | additions
diff --git a/q3.tex b/q3.tex
index 9fdeca6..9275a24 100644
--- a/q3.tex
+++ b/q3.tex
...
So the number of edges that cross A and B = sum of the number of edges added by the $End$ nodes...
Which is
replace_contentgt;=\sum\limits_{i=1}^n $\sum\limits_{i=1}^n \frac{e_i}{2} = E$ (since this is how much the greedy algorithm adds each time)...
Which is
replace_contentgt;= \frac{E}{2}$ (since $\frac{E}{2}$ since the sum of the $e_i$’s equal the total number of
edges). edges.
So the number of edges that cross A and B from the greedy algo is
replace_contentgt;= \frac{E}{2}$ $\frac{E}{2}$. Since the optimal value can only be $E$ at best that means this greedy algorithm is at most 2 times worse than the optimal solution.
\textbf{4.}