Vertex Cover Approximation

[@arthur.s]

Incredibly high quality video, thank you very much!

[@user-fb4iv4me6g]

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?

[@discoETH]

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.