5:12. If C* is the optimal solution. How come we say C*>=C? Why would the optimal solution be larger or equal to the approx solution? Shouldn't it be the other way around?
the statement c* >= c is correct in this context. Since the blue edges (c=3) are sufficiently apart in the example, we need at least 3 (c*) nodes to cover these edges. This is generally true. If some c edges do not share any node, c* is at least as large as c.
Incredibly high quality video, thank you very much!
5:12. If C* is the optimal solution. How come we say C*>=C? Why would the optimal solution be larger or equal to the approx solution? Shouldn't it be the other way around?
the statement c* >= c is correct in this context. Since the blue edges (c=3) are sufficiently apart in the example, we need at least 3 (c*) nodes to cover these edges. This is generally true. If some c edges do not share any node, c* is at least as large as c.