- Let x be a min-cost fractional vertex cover.
- Return the set S of vertices v having x(v) ≥ 1/2.

**prove:** *The set S of vertices is a vertex cover.*

**prove:** *The cost of S is at most twice the minimum cost of any vertex cover.*

**prove:** *The IntegralityGap of the above integer linear program for min-cost vertex cover is 2.*