information:highlighting, linguistic:voice_change, stylistic:tone
ILP formulation

Assume that every vertex has an associated cost of c (v) ≥ 0 {\displaystyle c(v)\geq 0}.The (weighted) minimum vertex cover problem can be formulated as the following integer linear program (ILP).

This ILP belongs to the more general class of ILPs for covering problems.The integrality gap of this ILP is 2 {\displaystyle 2}, so its relaxation (allowing each variable to be in the interval from 0 to 1, rather than requiring the variables to be only 0 or 1) gives a factor- 2 {\displaystyle 2} approximation algorithm for the minimum vertex cover problem.Furthermore, the linear programming relaxation of that ILP is half-integral, that is, there exists an optimal solution for which each entry x v {\displaystyle x_{v}} is either 0, 1/2, or 1. A 2-approximate vertex cover can be obtained from this fractional solution by selecting the subset of vertices whose variables are nonzero.