this is for holding javascript data
Jeremy Ting edited q3.tex
almost 10 years ago
Commit id: 17a5db527e24e9125b91423733a9c7319342c3bb
deletions | additions
diff --git a/q3.tex b/q3.tex
index 48e4fb4..4656307 100644
--- a/q3.tex
+++ b/q3.tex
...
This is a 2-approximation algorithm. Let the total number of edges in the graph be $E$. Let $n$ be the number of nodes. For every single edge in the graph, it has two nodes. Let's label the first node as the $Start$ node and the other node at the $End$ node.
When the $End$ node gets added to the graph problem, the edge is created. Now let $e_i$ be the number of edges that the node $i$, is considered the $End$ node. Since every single edge has one $End$ node, that means
$\sum{i=1}{n} $\sum\limits_{i=1}^n e_i = E$the sum from i=1 to n of ei=E (which is the total number of edges)