Vertex Cover Approximation

Note on the Unique Games Conjecture: If the UCG is true then there is no polynomial-time algorithm that achieves a better approximation than 2 for vertex cover.

Weighted Vertex Cover via LP Relaxation

An approximation algorithm for the vertex cover problem can be created by looking at linear relaxations of the integer linear program formulation of vertex cover. First consider the following ILP: $$ \begin{alignat}{1} & \text{min} & \sum_{u\in V} a_ux_u \\ & \text{subject to} \quad& \forall u \in V\colon x_u = 0 \lor x_u = 1 & \\ & \text{and} \quad& \forall (v, w) \in E\colon x_v + x_w \ge 1 & \\ \end{alignat} $$ Now consider the linear relaxation: $$ \begin{alignat}{1} & \text{min} & \sum_{u\in V} a_ux_u^\ast \\ & \text{subject to} \quad& \forall u \in V\colon\, 0 \le x_u^\ast \le 1 & \\ & \text{and} \quad& \forall (v, w) \in E\colon x_v^\ast + x_w^\ast \ge 1 & \\ \end{alignat} $$ Solving integer linear programs is NP-hard, linear programs can however be solved in polynomial time. By solving this LP and rounding we have an efficient approximation algorithm. $$ z_u = 1 \text{ if } x_u^\ast \ge 0.5 \text{ else } 0 $$ Correctness: For any solution to the LP and any edge \((v, w)\) the constraint \(x_v^\ast + x_w^\ast \ge 1\) must hold. Therefore one of \(x_v^\ast, x_w^\ast\) must be greater or equals 0.5 and at least one of the vertices is included in the vertex cover.

Quality guarantee: \(\text{Output cost} = \sum_{u} a_uz_u \le 2\sum_{u} a_ux_u^\ast \le 2\text{OPT}\). (our solution is better than two times the linear relaxation, and the LR achieves a higher optimization value than OPT)

In typical cases the performance is within 10% of OPT. To quantify the degree of deviation from OPT we can compare our output cost to the cost of our linear relaxation \(\sum_{u} a_ux_u^\ast\) (which is lower than opt). If our output cost is within \(x%\) of of the linear relaxation cost it must also be within \(x%\) of OPT.

Overall we have: \(\sum_{u} a_ux_u^\ast \le \text{OPT} \le \sum_{u} a_uz_u \le 2\sum_{u} a_ux_u^\ast \le 2\text{OPT}\)

Note: There is a 3/2-approximation algorithm for vertex cover on 4-colorable graphs via a specific rounding procedure that uses the coloring and above linear relaxation.

Vertex Cover via Maximal Matching

A matching (or independent edge set) of a graph is a subset of the edges of the graph such that no edges share a vertex.
A maximal matching is a matching that is not a subset of any other matching. No additional edges can be added to a maximal matching.
A maximum matching (or maximum-cardinality matching) is a matching that contains the largest possible number of edges. Every maximum matching is a maximal matching. A maximum matching can be found in polynomial time using the blossom algorithm which uses augmenting paths (paths that alternate between edges in the matching and edges not in the matching).
A perfect matching is a matching that matches all of the vertices of the graph.

2-OPT Approximation for Vertex Cover via Matching:
  1. Compute a maximal matching
  2. For each edge in the matching add both vertices to the vertex cover.

Knapsack Approximation and Rounding

Definition: A polynomial-time approximation scheme (PTAS) is an polynomial time approximation algorithm that can find solutions within a factor \(1+\epsilon\) (or \(1-\epsilon\) for maximization) of optimality.
Definition: A fully polynomial-time approximation scheme (FPTAS) is an approximation scheme that is not only polynomial in \(N\) but also in \(1/\epsilon\).
Theorem: The knapsack problem admits a fully polynomial-time approximation scheme.

Special Cases

Theorem: In the special case where \(w_i = v_i\), the greedy algorithm that picks the maximum value item is a 2-approximation.
Theorem: The special case where \(w_i = v_i\) and \(v_i \in \{1, 2, \ldots, B\}\) where \(B\) is a small integer polynomial in \(n\), can be solved in polynomial time with dynamic programming.
Theorem: The special case where all \(w_i, v_i \in \{1, 2, \ldots, N\}\) where \(N\) is a small integer polynomial in \(n\) can be solved time proportional to \(\mathcal{O}(n^2N)\) (or pseudo-polynomial if \(N\) is not polynomial in \(n\)).

Scale & Round FPTAS for Knapsack

This algorithm exploits the fact that when \(v_i, w_i\) are small integers polynomial in \(n\) we can solve the Knapsack problem optimally in polynomial time with dynamic programming.
  1. Discard items that don't fit in the knapsack at all.
  2. Scale values linearly such that the largest item has value \(N\) and round them down to the nearest integer. Weights are left unchanged - the DP table size is only proportional to [number of items \(\times\) value].
  3. Use the DP algorithm above to solve this problem.

\(N\) has to be chosen in such a way that the runtime is polynomial but the approximation is close to optimal. Note that unlike in the vertex cover approximation above we round the inputs, not the outputs.

Correctness: The algorithm produces only feasible solutions (with total weight less or equal than the knapsack capacity) since weights are left unchanged by the scale and round procedure.

Quality guarantee:
Let \(S\) be the set of items returned by our algorithm and \(S^\ast\) by the set of items returned by the optimal solution to the unmodified problem. Note that \(S^\ast\) is also optimal for the scaled but unrounded problem, since scaling does not affect the problem structure.
We know that (where \(\alpha\) is the scaling factor) $$ \begin{equation} \begin{aligned} \text{Value}(S) &= \sum_S v_i\\ &= \frac{1}{\alpha} \sum_S \alpha v_i\\ & \ge \frac{1}{\alpha} \sum_S v_i' \end{aligned} \end{equation} $$ since \(v_i' = \lfloor \alpha v_i \rfloor\). We also know that $$ \sum_S v_i' \ge \sum_{S^\ast} v_i' $$ since \(S\) is optimal for the scaled and rounded instance. Due to rounding it holds that \(v_i' > \alpha v_i-1\), so \(\sum_{S^\ast} v_i' > \alpha \sum_{S^\ast} v_i-n\) where \(\sum_{S^\ast} v_i = \text{OPT}\).

Overall: $$ \begin{equation} \begin{aligned} \text{Value}(S) &= \sum_S v_i\\ &= \frac{1}{\alpha} \sum_S \alpha v_i\\ & \ge \frac{1}{\alpha} \sum_S v_i'\\ & \ge \frac{1}{\alpha} \sum_{S^\ast} v_i'\\ & \ge \sum_{S^\ast} v_i - \frac{n}{\alpha}\\ & = \text{OPT} - \frac{n}{\alpha}\\ & = \text{OPT} - \frac{n \max v_i}{N}\\ & \ge \text{OPT} - \frac{n}{N}\text{OPT} \end{aligned} \end{equation} $$ So for \(N=100n\) we will have an approximation of \((1-\frac{1}{100})\text{ OPT} = 0.99 \text{ OPT}\). The algorithm has a runtime of \(\mathcal{O}(n^2N)\).

Partial Brute-Force PTAS for Knapsack

The knapsack problem admits another polynomial time approximation scheme. Here we first find part of the solution by brute-force and then finish up using a greedy algorithm. This algorithm has a runtime of \(\mathcal{O}(\frac{1}{\epsilon}n^{1/\epsilon})\) and achieves an approximation within a factor of \(1+\frac{1}{k}\) of optimality where \(k\) is the largest possible subset we consider in the brute-force step.
For more details see this excellent paper.