1. Formal Invariant — Lower-Bound Certificates & Value Scaling
1. Unweighted Vertex Cover 2-Approximation (Maximal Matching Lower Bound)
Greedily pick any uncovered edge $(u, v) \in E$, add both $u$ and $v$ to cover $C$, and delete all edges incident to $u$ or $v$. The chosen edges form a matching $M$ (pairwise vertex-disjoint). Since every valid Vertex Cover must pick at least $1$ endpoint from each edge in $M$, we have $OPT \ge |M|$, while our cover has size $|C| = 2|M| \le 2 \cdot OPT$!
2. Metric TSP 2-Approximation & Christofides-Serdyukov 1.5-Approximation
When edge weights obey the Triangle Inequality $w(u, v) \le w(u, x) + w(x, v)$:
- Deleting one edge from the optimal tour $OPT$ gives a spanning tree, so $w(\text{MST}) \le OPT$. Doubling the MST and shortcutting repeated vertices via the Triangle Inequality gives a tour of cost $\le 2 \cdot w(\text{MST}) \le 2 \cdot OPT$.
- Christofides (1976): Instead of doubling the whole MST, find a Minimum-Weight Perfect Matching $M^*$ on the set $O$ of odd-degree vertices of the MST. By parity, $w(M^*) \le \frac{1}{2} OPT$, so the Eulerian tour of $\text{MST} \cup M^*$ has cost $\le w(\text{MST}) + w(M^*) \le 1.5 \cdot OPT$!
3. 0-1 Knapsack FPTAS (Fully Polynomial-Time Approximation Scheme)
Let $v_{\max} = \max_i v_i$ and scale down every item's value by $K = \frac{\varepsilon \cdot v_{\max}}{N}$: $\tilde{v}_i = \lfloor v_i / K \rfloor$. Now $\max_i \tilde{v}_i = \lfloor N / \varepsilon \rfloor$, so the total scaled value of any subset is at most $N \cdot (N / \varepsilon) = N^2 / \varepsilon$. Running minimum-weight DP indexed by scaled value takes $O(N^3 / \varepsilon)$ time and loses at most $N \cdot K = \varepsilon \cdot v_{\max} \le \varepsilon \cdot OPT$!
2. The Inapproximability Spectrum
FPTAS: (1 - eps) in O(N^3 / eps)"] --> ConstApprox["Metric TSP (1.5-Approx)
Vertex Cover (2-Approx)
MAX-3SAT (7/8-Approx)"] ConstApprox --> LogApprox["Set Cover
Greedy H_n <= (ln n + 1)-Approx
(Tight under P != NP)"] LogApprox --> Inapprox["General TSP (No Triangle Ineq)
& Maximum Clique
Inapproximable within any poly factor!"]
3. Why General TSP (Without Triangle Inequality) Is Completely Inapproximable
Gap-Introducing Reduction from Hamiltonian Cycle
Suppose a polynomial-time algorithm could approximate General TSP within any factor $\rho \ge 1$. Given a graph $G = (V, E)$ for Hamiltonian Cycle, assign weight $1$ to every edge in $E$ and weight $\rho N + 1$ to every non-edge! If $G$ has a Hamiltonian cycle, $OPT = N$, so the $\rho$-approximation must return a tour of cost $\le \rho N$ (using only edges of weight $1$). If $G$ has no Hamiltonian cycle, any tour uses at least one non-edge and costs $\ge \rho N + N > \rho N$. Thus a $\rho$-approximation for General TSP would solve NP-Complete Hamiltonian Cycle in polynomial time!
4. Complexity & Approximation Ratio Matrix
Simulate Karger random multigraph edge contractions down to 2 supernodes, 3-SAT ≤_p Vertex Cover gadget graphs, and Knapsack FPTAS value-bucket scaling K = εP/n.
Invariant & State
| Optimization Problem | Approximation Algorithm | Guarantee Ratio | Time Complexity |
|---|---|---|---|
| Minimum Vertex Cover | Maximal Matching / LP Pricing | $2 \cdot OPT$ | O(V + E) |
| Metric TSP (Triangle Inequality) | Twice-Around-the-Tree (MST) | $2 \cdot OPT$ | O(E log V) |
| Metric TSP (Triangle Inequality) | Christofides (MST + Odd MWPM) | $1.5 \cdot OPT$ | O(V^3) |
| Minimum Set Cover ($n$ elements) | Greedy Min Cost per New Element | $H_n \approx (\ln n + 1) \cdot OPT$ | O(n * m) |
| 0-1 Knapsack (FPTAS) | Value Scaling $\tilde{v}_i = \lfloor v_i / K \rfloor$ | $(1 - \varepsilon) \cdot OPT$ | O(N^3 / eps) |
5. Production-Grade C++20 Implementation (2-Approx Vertex Cover & Knapsack FPTAS)
#include <vector>
#include <cstdint>
#include <cmath>
#include <limits>
#include <algorithm>
// 1. Linear-Time 2-Approximation for Minimum Unweighted Vertex Cover via Maximal Matching
std::vector<int> vertex_cover_2approx(int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<bool> in_cover(n, false);
std::vector<int> cover;
for (const auto& [u, v] : edges) {
if (!in_cover[u] && !in_cover[v]) {
in_cover[u] = true;
in_cover[v] = true;
cover.push_back(u);
cover.push_back(v);
}
}
return cover; // Guaranteed: cover.size() <= 2 * OPT
}
// 2. 0-1 Knapsack FPTAS: Returns a subset value >= (1 - eps) * OPT in O(N^3 / eps) time
int64_t knapsack_fptas(const std::vector<int64_t>& weights,
const std::vector<int64_t>& values,
int64_t capacity,
double eps) {
const int n = static_cast<int>(weights.size());
int64_t v_max = 0;
for (int i = 0; i < n; ++i) {
if (weights[i] <= capacity) v_max = std::max(v_max, values[i]);
}
if (v_max == 0) return 0;
double K = (eps * static_cast<double>(v_max)) / static_cast<double>(n);
if (K < 1.0) K = 1.0; // Exact DP when K == 1
std::vector<int> scaled_v(n, 0);
int max_scaled_sum = 0;
for (int i = 0; i < n; ++i) {
if (weights[i] <= capacity) {
scaled_v[i] = static_cast<int>(std::floor(values[i] / K));
max_scaled_sum += scaled_v[i];
}
}
constexpr int64_t INF = std::numeric_limits<int64_t>::max() / 4;
// dp[v] = minimum weight required to achieve scaled value v
std::vector<int64_t> dp(max_scaled_sum + 1, INF);
std::vector<int64_t> real_val(max_scaled_sum + 1, 0);
dp[0] = 0;
int cur_max_v = 0;
for (int i = 0; i < n; ++i) {
if (weights[i] > capacity) continue;
int sv = scaled_v[i];
for (int v = cur_max_v; v >= 0; --v) {
if (dp[v] + weights[i] <= capacity && dp[v] + weights[i] < dp[v + sv]) {
dp[v + sv] = dp[v] + weights[i];
real_val[v + sv] = std::max(real_val[v + sv], real_val[v] + values[i]);
}
}
cur_max_v += sv;
}
int64_t best = 0;
for (int v = 0; v <= max_scaled_sum; ++v) {
if (dp[v] <= capacity) best = std::max(best, real_val[v]);
}
return best;
}Production Pitfall — Why Greedy Max-Degree Vertex Cover Is NOT a 2-Approximation
It is tempting to approximate Minimum Vertex Cover by repeatedly picking the vertex of highest remaining degree (just like Greedy Set Cover). Shockingly, Greedy Max-Degree Vertex Cover is NOT a constant-factor approximation—on bipartite graphs constructed with degree-harmonic layers, it returns a cover of size $\Theta(\log N) \cdot OPT$! By contrast, the seemingly 'dumber' algorithm that picks both endpoints of any maximal matching is guaranteed to be within $2 \cdot OPT$.