this is for holding javascript data
Jeremy Ting edited q3.tex
almost 10 years ago
Commit id: 8f438c98cebeab8d4e1f9377a55abec3d7420a09
deletions | additions
diff --git a/q3.tex b/q3.tex
index 9a28b73..fee70f3 100644
--- a/q3.tex
+++ b/q3.tex
...
To show that it provides a 2-approximation solution:
First we know that the sum of all the edges weights
replace_contentgt;=$ >= optimal
value.S ince value. Since the cost is derived from the number of edges, it can’t exceed the sum of the edge weights. Also we know that if we reached a locally optimal solution, that means if you swap two vertices, the total cost must decrease.
Let's call our two sets be call $A$ and $B$. If we are a locally optimum solution and we move the node u from A to B, we get:
\sum\nolimits_{P_i \in Paths(I)} Probes(P_{i})