Let be the number of edges,
and let be the size of an
optimal vertex cover.
At any point, suppose there are uncovered edges remaining. Since an
optimal cover of size can cover
all these edges, by averaging,
some vertex in the optimal solution is incident to at least of the remaining edges. Therefore
the maximum-degree vertex among the remaining graph is incident to at
least uncovered edges as
well.
If the algorithm picks such a highest-degree vertex, then after one
step the number of remaining uncovered edges is at most After steps, the number
of uncovered edges is at most To make this less than ,
it is enough to have that is, Hence the algorithm picks at most vertices, so it is an approximation.
Note: this proof is for the greedy algorithm that repeatedly picks
the vertex covering the largest number of uncovered edges.
-approximation
Let be a maximal matching in
the graph, and let be the set of
all endpoints of edges in . Then
We first show that is a vertex
cover. Suppose not. Then there exists an edge such that neither nor is in . That means neither nor is matched by any edge in . But then we could add to , contradicting the maximality of . Hence is a vertex cover.
Now compare with the optimum vertex cover . Since the edges in are pairwise disjoint, any vertex cover
must cover each edge of using at
least one distinct endpoint. Therefore every vertex cover, in particular
an optimal one, must contain at least vertices. So
Combining the two inequalities,
Therefore, taking all endpoints of a maximal matching yields a for Minimum Vertex Cover.
Knapsack
-approximation
Sort items by non-increasing density . Let be the set obtained by greedily taking
items in that order as long as they fit. Let be the first item that does not fit.
Also consider the single feasible item of maximum value, and return the
better of these two choices.
Let be the value of the
fractional knapsack optimum. Since fractional knapsack follows the same
density order, it takes all items in and then possibly a fraction of item
. Therefore Hence Since every integral solution is also feasible for the
fractional relaxation, Therefore the returned solution has value at least So this algorithm is a -approximation.
Hitting Set
-approximation
Assume every set has size at most , i.e.
Consider the LP relaxation: Let be an optimal LP
solution. The rounding algorithm selects every element such that
Feasibility
Fix any set . Since and , it is
impossible that every element in has because then a contradiction. So each set contains at least one selected
element, and the rounded solution is a valid hitting set.
Approximation ratio
Let be the rounded set. For
every , Thus Since the LP optimum is at most the integer optimum, Therefore So the rounding algorithm is an
