ii. Approximation Algorithms

When exact optimization is NP-hard, settle for a provable ratio. An algorithm is a $\rho$-approximation if on every input $\frac{\mathrm{ALG}}{\mathrm{OPT}}\le \rho$ (minimization) or $\ge \rho$ (maximization). Two lessons: the achievable ratio varies enormously between superficially similar problems, and many of the best ratios are provably optimal (assuming $\mathrm{P}\ne \mathrm{NP}$ or the Unique Games Conjecture).

Problem	Best ratio	Hardness
vertex cover	2	NP-hard below $\sqrt{2}$; $2-\epsilon$ under UGC
metric TSP	$\frac{3}{2}$ (Christofides), $\frac{3}{2}-10^{-36}$ (2021)	no PTAS
Euclidean TSP	$1+\epsilon$ (Arora’s PTAS)
general TSP	none	no constant factor unless P = NP
set cover	$\ln n$ (greedy)	$(1-\epsilon )\ln n$ is NP-hard
max cut	0.878 (Goemans–Williamson)	optimal under UGC; NP-hard above $\frac{16}{17}$
max SAT	0.797
knapsack	FPTAS $1+\epsilon$
bin packing	$\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$ (FFD); asymptotic PTAS	absolute $<\frac{3}{2}$ NP-hard
makespan ($m$ identical machines)	$\frac{4}{3}-\frac{1}{3m}$ (LPT); PTAS
max independent set	$O(n/{\log }^{2}n)$	$n^{1-\epsilon }$: essentially inapproximable
Steiner tree	$\ln 4+\epsilon \approx 1.386$
facility location (metric)	1.488	1.463
$k$-center	2 (farthest point)	$2-\epsilon$ NP-hard
max coverage, monotone submodular with cardinality	$1-\frac{1}{e}$ (greedy)	optimal unless P = NP

Class	Running time	Example
PTAS	polynomial for each fixed $\epsilon$ (may be $n^{1/\epsilon }$)	Euclidean TSP, makespan
FPTAS	polynomial in $n$ and $\frac{1}{\epsilon }$	knapsack, subset sum
APX	some constant factor	vertex cover, metric TSP
no constant factor		general TSP, max clique

A strongly NP-hard problem has no FPTAS unless P = NP (an FPTAS with $\epsilon <\frac{1}{\mathrm{OPT}}$, OPT bounded by a polynomial in the numbers, would solve it exactly); knapsack has one because it is only weakly NP-hard (Complexity Theory).

Techniques

Technique	Idea	Examples
greedy with a bound	locally best choices, charged against OPT	set cover, vertex cover, $k$-center, max coverage, LPT, FFD
lower-bounding OPT	find $L\le \mathrm{OPT}$ with $\mathrm{ALG}\le \rho L$	MST for TSP, a matching for vertex cover
LP relaxation + rounding	the LP value bounds OPT; round the fractional optimum	vertex cover (half-integral), set cover, scheduling on unrelated machines (Lenstra–Shmoys–Tardos, 2)
randomized rounding	treat fractional values as probabilities; Chernoff for constraints	set cover $O(\log n)$, congestion $O(\log n/\log \log n)$ (Raghavan–Thompson), MAX-SAT $\frac{3}{4}$
SDP + hyperplane rounding	vectors instead of $\pm 1$	max cut 0.878, MAX-2SAT, MAX-DICUT, correlation clustering
primal–dual	build a solution and a dual certificate together; weak duality gives the ratio	facility location, Steiner forest
local search	improve while possible; sum the local-optimality inequalities	max cut $\frac{1}{2}$, $k$-median
DP + rounding (FPTAS)	round numbers so a pseudo-polynomial DP becomes small	knapsack
matroids: greedy is exact	no approximation needed	spanning trees, linear bases, unit jobs with deadlines: Matroids

Proving a ratio, the standard shapes: charging (assign each unit of ALG’s cost to something OPT must pay for), lower-bounding OPT, local optimality (no improving move: sum those inequalities), LP duality (a feasible dual bounds OPT). Matroid intersection of two matroids is polynomial; of three it is NP-hard.

In contests approximation ratios rarely appear directly (problems want exact answers); the ideas help in marathon problems (a ratio justifies a construction), to bound a greedy’s quality and decide whether it can be optimal, to recognise APX-hard problems and stop searching for an exact polynomial algorithm, in branch and bound (an approximation is a good incumbent and pruning bound), and in constructive tasks that really ask for “any solution within $k$ of optimal”.

Greedy algorithms with guarantees

Problem	Greedy rule	Ratio
set cover (weighted: best cost per new element)	most uncovered elements	$H_n\approx \ln n$
vertex cover	both endpoints of an uncovered edge	2
metric TSP	double the MST, shortcut	2
metric TSP	Christofides	$\frac{3}{2}$
max cut	local search: move any vertex that improves the cut	$\frac{1}{2}$
makespan	least-loaded machine (any order) / LPT (longest first)	$2-\frac{1}{m}$ / $\frac{4}{3}-\frac{1}{3m}$
bin packing	first fit decreasing	$\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$
$k$-center	farthest point (Gonzalez)	2
max coverage ($k$ sets), monotone submodular	largest marginal gain	$1-\frac{1}{e}\approx 0.632$ (Nemhauser–Wolsey–Fisher)
Steiner tree	MST of the metric closure on the terminals	2
knapsack	ratio order, or the best single item	2

The "obvious" greedy is worse

For vertex cover, repeatedly taking the highest-degree vertex feels better but is only $\Theta (\log n)$-approximate; taking both endpoints of an uncovered edge is 2-approximate. Intuition is not a proof. Similarly, nearest-neighbour TSP is only $\Theta (\log n)$.

vector<int> greedySetCover(int n, const vector<vector<int>>& sets) {   // elements 0..n-1; H_n-approximation
    vector<char> covered(n, 0); vector<int> chosen; int remaining = n;
    while (remaining > 0) {
        int best = -1, bestGain = 0;
        for (int i = 0; i < sz(sets); i++) {
            int gain = 0; for (int e : sets[i]) gain += !covered[e];
            if (gain > bestGain) bestGain = gain, best = i;
        }
        if (best < 0) break;                                 // infeasible
        for (int e : sets[best]) if (!covered[e]) covered[e] = 1, remaining--;
        chosen.push_back(best);
    }
    return chosen;
}
 
vector<int> vertexCover2(int n, const vector<pair<int, int>>& edges) {   // 2-approximation (maximal matching)
    vector<char> in(n, 0); vector<int> cover;
    for (auto [u, v] : edges) if (!in[u] && !in[v]) { in[u] = in[v] = 1; cover.push_back(u); cover.push_back(v); }
    return cover;
}
 
vector<int> kCenterGonzalez(const vector<vector<double>>& d, int k) {   // 2-approximation of the min max radius
    int n = sz(d); vector<int> centers{0}; vector<double> dist = d[0];
    while (sz(centers) < min(k, n)) {
        int far = int(max_element(all(dist)) - dist.begin());
        centers.push_back(far);
        for (int i = 0; i < n; i++) dist[i] = min(dist[i], d[far][i]);
    }
    return centers;
}
 
ll lptMakespan(vector<ll> p, int m) {                        // longest processing time first
    sort(all(p), greater<ll>());
    priority_queue<ll, vector<ll>, greater<ll>> load; for (int i = 0; i < m; i++) load.push(0);
    for (ll x : p) { ll l = load.top(); load.pop(); load.push(l + x); }
    ll mx = 0; while (!load.empty()) mx = max(mx, load.top()), load.pop();
    return mx;
}
 
int firstFitDecreasing(vector<double> w) {                   // bins of capacity 1
    sort(all(w), greater<double>()); vector<double> bins;
    for (double x : w) {
        bool placed = false;
        for (auto& b : bins) if (b + x <= 1 + 1e-12) { b += x; placed = true; break; }
        if (!placed) bins.push_back(x);
    }
    return sz(bins);
}
 
vector<int> greedyMaxCoverage(int n, const vector<vector<int>>& sets, int k) {   // (1 - 1/e)-approximation
    vector<char> covered(n, 0); vector<int> chosen;
    for (int t = 0; t < k; t++) {
        int best = -1, bestGain = -1;
        for (int i = 0; i < sz(sets); i++) { int g = 0; for (int e : sets[i]) g += !covered[e]; if (g > bestGain) bestGain = g, best = i; }
        if (best < 0) break;
        for (int e : sets[best]) covered[e] = 1;
        chosen.push_back(best);
    }
    return chosen;
}

Proof: the greedy ratios

Set cover, $H_n$. When an element is covered, charge it $\frac{1}{\text{gain}}$ (the chosen set’s unit cost spread over its new elements); the total charge is the number of sets chosen. If OPT uses $k$ sets, at any moment those $k$ sets cover the $r$ remaining elements, so some set covers at least $\frac{r}{k}$ of them and the greedy gain is $\ge \frac{r}{k}$. The element covered when $r$ remain is charged $\le \frac{k}{r}$; summing over $r=n,\dots ,1$ gives $\le k{H}_n$. No polynomial algorithm achieves $(1-\epsilon )\ln n$ unless P = NP (Dinur–Steurer, 2014).

Vertex cover, 2. The edges whose both endpoints were taken form a matching $M$; every cover contains an endpoint of each matching edge, distinct for distinct edges, so $\mathrm{OPT}\ge |M|=\frac{\mathrm{ALG}}{2}$. The output is a cover: an edge left uncovered would have been taken.

$k$-center, 2. Let $r$ be the final maximum distance to the nearest centre and $p$ a point attaining it. The $k$ centres and $p$ are $k+1$ points pairwise at distance $\ge r$ (each centre was the farthest point when chosen). Two of them share a cluster of an optimal solution, so their distance is at most $2\mathrm{OPT}$ (triangle inequality through that cluster’s centre): $r\le 2\mathrm{OPT}$. Doing better than 2 is NP-hard (Hsu–Nemhauser).

LPT, $\frac{4}{3}-\frac{1}{3m}$. Let job $j$ (processing time $p_j$) finish last, and drop the jobs after it (this does not change the makespan and does not increase OPT). It started at most at the average load of the others, $\le \frac{\sum p-p_j}{m}$, so $\mathrm{ALG}\le \frac{\sum p}{m}+p_j(1-\frac{1}{m})\le \mathrm{OPT}+p_j(1-\frac{1}{m})$. If $p_j\le \frac{\mathrm{OPT}}{3}$ this is the bound. Otherwise every job exceeds $\frac{\mathrm{OPT}}{3}$, so an optimal schedule has at most two jobs per machine and at most $2m$ jobs; then pairing the $i$-th largest with the $(2m+1-i)$-th largest (padding with zeros) is optimal by an exchange argument, and LPT produces exactly this pairing (jobs $\mathrm{1..}m$ on separate machines, then each next job onto the currently least-loaded machine, which holds the smallest of the first $m$). The plain least-loaded rule in any order gives $2-\frac{1}{m}$ by the same first inequality with $p_j\le \mathrm{OPT}$.

Max coverage, $1-\frac{1}{e}$. Let OPT cover $c^{\ast }$ and greedy cover $c_i$ after $i$ steps. The $k$ optimal sets cover at least $c^{\ast }-c_i$ uncovered elements, so one covers $\ge \frac{c^{\ast }-c_i}{k}$, and $c^{\ast }-c_{i+1}\le (1-\frac{1}{k})(c^{\ast }-c_i)$. After $k$ steps $c^{\ast }-c_k\le (1-\frac{1}{k}{)}^k{c}^{\ast }\le \frac{c^{\ast }}{e}$. The same argument works for any monotone submodular function (diminishing returns: $f(S\cup \{x\})-f(S)$ shrinks as $S$ grows): coverage, influence spread, sensor placement, feature selection.

FFD satisfies $\mathrm{FFD}\le \frac{11}{9}\mathrm{OPT}+\frac{6}{9}$ (Johnson 1973, the tight additive constant by Dósa 2007); the proof is a long weighting argument and is quoted here. All routines were checked against exact optima by brute force on small random instances (set cover and max coverage up to 8 sets, vertex cover up to 12 vertices, $k$-center up to 9 points, LPT up to 9 jobs, FFD up to 9 items).

LP rounding, randomized rounding and the knapsack FPTAS

Vertex cover by LP: $\min \sum x_v$, $x_u+x_v\ge 1$ on edges, $0\le x\le 1$. Every vertex of this polytope is half-integral ($x_v\in \{0,\frac{1}{2},1\}$), so rounding $x_v\ge \frac{1}{2}$ up gives a 2-approximation directly (and the Nemhauser–Trotter kernel).

Randomized rounding (Raghavan–Thompson, 1987): (1) write an integer LP, (2) relax $x_i\in \{0,1\}$ to $[0,1]$ and solve (the LP value bounds OPT), (3) set $x_i=1$ independently with probability $x_i^{\ast }$, (4) the expected objective equals the LP value by linearity, and Chernoff bounds show constraints are nearly satisfied with high probability, (5) repair or repeat. For set cover, run $O(\log n)$ independent rounds: each costs LP in expectation, and an element is missed in one round with probability ${\prod }_{S\ni e}(1-x_S^{\ast })\le e^{-\sum x_S^{\ast }}\le e^{-1}$, so after $O(\log n)$ rounds all elements are covered with high probability (union bound): an $O(\log n)$-approximation, matching greedy and the hardness. The original application was global wire routing in VLSI: route many nets through a grid minimising maximum congestion; the fractional routing is a flow LP, and rounding each net to one random path keeps congestion within $O(\frac{\log n}{\log \log n})$ of optimal. Chernoff, in the form used there: $\mathrm{Pr}[\sum X_i\ge (1+\delta )\mu ]\le \exp (-\frac{{\delta }^2\mu }{2+\delta })$, $\mathrm{Pr}[\sum X_i\le (1-\delta )\mu ]\le \exp (-\frac{{\delta }^2\mu }{2})$ (Randomized Algorithms). Derandomization by conditional expectations with pessimistic estimators makes the rounding deterministic.

Problem	LP relaxation	Result
set cover	fractional cover	$O(\log n)$
vertex cover	fractional cover (half-integral)	2, deterministic rounding at $\frac{1}{2}$
congestion / multicommodity routing	fractional flow	$O(\log n/\log \log n)$, the original application
facility location	fractional assignment	constant factor with clustered rounding
scheduling on unrelated machines	assignment LP	2 (Lenstra–Shmoys–Tardos)
MAX-SAT	LP + biased coins	$\frac{3}{4}$

// (1 - eps)-approximation for 0/1 knapsack: scale values, then the value-indexed DP (min weight per value).
ll knapsackFPTAS(const vector<ll>& w, const vector<ll>& v, ll W, double eps) {
    int n = sz(w); ll vmax = 0; for (int i = 0; i < n; i++) if (w[i] <= W) vmax = max(vmax, v[i]);
    if (vmax == 0) return 0;
    double K = max(1.0, eps * vmax / n);
    vector<ll> sv(n); ll total = 0;
    for (int i = 0; i < n; i++) sv[i] = w[i] <= W ? (ll)(v[i] / K) : 0, total += sv[i];
    const ll INF = LLONG_MAX / 4; vector<ll> dp(total + 1, INF); vector<vector<char>> take(n, vector<char>(total + 1, 0)); dp[0] = 0;
    for (int i = 0; i < n; i++) if (w[i] <= W && sv[i] > 0)
        for (ll s = total; s >= sv[i]; s--) if (dp[s - sv[i]] + w[i] < dp[s]) dp[s] = dp[s - sv[i]] + w[i], take[i][s] = 1;
    ll best = 0; for (ll s = total; s >= 0; s--) if (dp[s] <= W) { best = s; break; }
    ll value = 0;                                            // recover the chosen items, return their true value
    for (int i = n - 1; i >= 0 && best > 0; i--) if (take[i][best]) value += v[i], best -= sv[i];
    return value;
}

Proof: half-integrality, and the FPTAS guarantee

Half-integrality. Let $x$ be a vertex of the polytope with some value outside $\{0,\frac{1}{2},1\}$. Let $A=\{v:0<x_v<\frac{1}{2}\}$, $B=\{v:\frac{1}{2}<x_v<1\}$, and define $x^{\pm }$ by adding $\pm \epsilon$ on $A$ and $\mp \epsilon$ on $B$. For small $\epsilon$ both stay in $[0,1]$, and every edge constraint stays satisfied: a tight edge ($x_u+x_v=1$) with one endpoint in $A$ has the other in $B$ (changes cancel), and non-tight edges have slack. Then $x=\frac{1}{2}(x^{+}+x^{-})$ is not a vertex: contradiction. Rounding: every edge has an endpoint with $x\ge \frac{1}{2}$, and the rounded cost is $\le 2\sum x_v=2\mathrm{LP}\le 2\mathrm{OPT}$.

FPTAS. With $K=\frac{\epsilon v_{\max }}{n}$ (where $v_{\max }\le \mathrm{OPT}$, since any single fitting item is a solution), each scaled value loses less than 1, i.e. less than $K$ in true value. The DP finds the set $S$ maximizing the scaled value exactly; for the optimal set $O$, ${\sum }_{S}v\ge K{\sum }_S\lfloor v/K\rfloor \ge K{\sum }_O\lfloor v/K\rfloor \ge {\sum }_{O}v-nK=\mathrm{OPT}-\epsilon v_{\max }\ge (1-\epsilon )\mathrm{OPT}$. Scaled values are at most $\frac{n}{\epsilon }$, so the DP has $O(\frac{n^2}{\epsilon })$ states per item and $O(\frac{n^3}{\epsilon })$ total. Checked against exact DP: the returned value is always $\ge (1-\epsilon )\mathrm{OPT}$.

Metric TSP: double tree and Christofides

Christofides (1976): (1) a minimum spanning tree $T$; (2) $O$ = vertices of odd degree in $T$ ($|O|$ even by the handshake lemma); (3) a minimum-weight perfect matching $M$ on $O$ ($O(n^3)$ via weighted blossom); (4) $T\cup M$ has all degrees even: take an Euler circuit (Hierholzer); (5) shortcut repeated vertices (never more expensive by the triangle inequality). $O(n^3)$ time, $O(n^2)$ space. The double-tree algorithm skips the matching (double every MST edge): ratio 2 in $O(n^2)$. Without the triangle inequality TSP has no constant-factor approximation unless P = NP (set non-edges to a huge weight and a $c$-approximation decides Hamiltonian cycle).

Method	Ratio	Time
nearest neighbour	$\Theta (\log n)$	$O(n^2)$
double tree	2	$O(n^2)$
Christofides	$\frac{3}{2}$	$O(n^3)$
Karlin–Klein–Oveis Gharan (2021)	$\frac{3}{2}-10^{-36}$	polynomial
Held–Karp	exact	$O(2^n{n}^2)$: Hamiltonian Paths and TSP
2-opt / Or-opt / Lin–Kernighan	no guarantee	fast; within 1–2% of optimal on real instances: Heuristic Optimization

Nobody runs Christofides on real instances; it matters for the guarantee. The code below uses a bitmask DP for the matching, enough to verify the algorithm on small instances (use weighted blossom beyond about 20 odd vertices).

double tourCost(const vector<vector<double>>& d, const vector<int>& t) { double s = 0; for (int i = 0; i < sz(t); i++) s += d[t[i]][t[(i + 1) % sz(t)]]; return s; }
 
vector<int> christofides(const vector<vector<double>>& d) {   // metric d; matching by bitmask DP (<= ~20 odd vertices)
    int n = sz(d); if (n <= 2) { vector<int> t(n); iota(all(t), 0); return t; }
    vector<int> par(n, -1); vector<double> best(n, 1e18); vector<char> in(n, 0); best[0] = 0;
    vector<vector<int>> g(n);
    for (int it = 0; it < n; it++) {                         // Prim, O(n^2)
        int u = -1; for (int v = 0; v < n; v++) if (!in[v] && (u < 0 || best[v] < best[u])) u = v;
        in[u] = 1; if (par[u] >= 0) g[u].push_back(par[u]), g[par[u]].push_back(u);
        for (int v = 0; v < n; v++) if (!in[v] && d[u][v] < best[v]) best[v] = d[u][v], par[v] = u;
    }
    vector<int> odd; for (int v = 0; v < n; v++) if (sz(g[v]) % 2) odd.push_back(v);
    int k = sz(odd); vector<double> dp(1 << k, 1e18); vector<int> choice(1 << k, -1); dp[0] = 0;
    for (int mask = 0; mask < (1 << k); mask++) {            // pair the lowest unmatched odd vertex
        if (dp[mask] >= 1e17) continue;
        int i = 0; while (i < k && (mask >> i & 1)) i++;
        if (i == k) continue;
        for (int j = i + 1; j < k; j++) if (!(mask >> j & 1)) {
            int nm = mask | 1 << i | 1 << j; double c = dp[mask] + d[odd[i]][odd[j]];
            if (c < dp[nm]) dp[nm] = c, choice[nm] = i * k + j;
        }
    }
    for (int mask = (1 << k) - 1; mask; ) { int i = choice[mask] / k, j = choice[mask] % k; g[odd[i]].push_back(odd[j]); g[odd[j]].push_back(odd[i]); mask ^= 1 << i | 1 << j; }
    vector<int> st{0}, circuit; vector<multiset<int>> adj(n); for (int v = 0; v < n; v++) for (int u : g[v]) adj[v].insert(u);
    while (!st.empty()) {                                    // Hierholzer on the multigraph T + M
        int v = st.back();
        if (adj[v].empty()) { circuit.push_back(v); st.pop_back(); }
        else { int u = *adj[v].begin(); adj[v].erase(adj[v].begin()); adj[u].erase(adj[u].find(v)); st.push_back(u); }
    }
    vector<int> tour; vector<char> seen(n, 0);
    for (int v : circuit) if (!seen[v]) seen[v] = 1, tour.push_back(v);   // shortcut
    return tour;
}

Proof: the 2 and 3/2 ratios

(a) $w(T)\le \mathrm{OPT}$: deleting an edge of the optimal tour leaves a spanning path, a spanning tree. Double tree: the doubled tree has an Euler circuit of cost $2w(T)$, and shortcutting never increases the cost (triangle inequality): $\le 2\mathrm{OPT}$. (b) $w(M)\le \frac{1}{2}\mathrm{OPT}$: shortcut the optimal tour to visit only $O$, in tour order: a cycle of cost $\le \mathrm{OPT}$ on an even number of vertices, which splits into two perfect matchings of $O$; the cheaper costs $\le \frac{1}{2}\mathrm{OPT}$, and the minimum matching is no heavier. (c) $T\cup M$ has even degrees (odd-degree vertices get one matching edge each), so it is Eulerian (connected because $T$ spans), with cost $w(T)+w(M)\le \frac{3}{2}\mathrm{OPT}$; shortcutting only helps. Checked against Held–Karp on random Euclidean instances with up to 11 points: the ratio never exceeded $\frac{3}{2}$.

Goemans–Williamson for MAX-CUT

MAX-CUT (partition the vertices to maximize the weight of crossing edges) is NP-hard and, unlike min cut, not solvable by flows. A random side for each vertex cuts each edge with probability $\frac{1}{2}$ (a 0.5-approximation in expectation), and local search also gives $\frac{1}{2}$. Goemans–Williamson (1994): write $\max \sum w_{ij}\frac{1-x_i{x}_j}{2}$ with $x_i=\pm 1$, relax each $x_i$ to a unit vector $v_i$ (a semidefinite program: the Gram matrix must be PSD, solvable to any precision in polynomial time by interior-point methods), then cut with a random hyperplane: $x_i=\mathrm{sign}⟨v_i,r⟩$ for a Gaussian $r$. Rounding costs $O(n^2)$ per trial (repeat and keep the best); the SDP is polynomial but heavy (a few thousand vertices), so this is not a contest tool: for MAX-CUT-flavoured contest problems use local search or simulated annealing. The template it established (integer program, convex relaxation, random rounding, bound the loss) also gives MAX-2SAT, MAX-DICUT, correlation clustering, sparsest cut and colouring results. Under the Unique Games Conjecture no polynomial algorithm beats 0.878 (Khot, Kindler, Mossel, O’Donnell); unconditionally, $\frac{16}{17}\approx 0.941$ is NP-hard.

Proof: 0.878

Two unit vectors at angle $\theta$ are separated by a random hyperplane with probability $\frac{\theta }{\pi }$: project onto their plane, where the hyperplane becomes a uniformly random line through the origin, which separates them iff its direction falls in an arc of total angle $2\theta$ out of $2\pi$. The SDP gains $\frac{1-\cos \theta }{2}$ from that edge, so each edge’s expected contribution is at least ${\min }_{0<\theta \le \pi }\frac{2\theta }{\pi (1-\cos \theta )}=0.87856\dots$ times its SDP contribution (minimum near $\theta \approx 2.331$ rad, $134°$). By linearity, $\mathbb{E}[\text{cut}]\ge 0.878\mathrm{SDP}\ge 0.878\mathrm{OPT}$, since the SDP is a relaxation.

Related notes

• Complexity Theory (inapproximability)
• Greedy and Exchange Arguments
• Linear Programming (duality, total unimodularity)