Chapter 39: Combinatorial Optimization

Why do some linear relaxations already have integral optimal solutions?

A discrete optimization problem chooses among combinatorial objects: matchings, flows, covers, independent sets, or cuts. An integer vector often records the chosen object. A relaxation permits a larger, continuous feasible set, making optimization easier while providing a bound on the discrete optimum. The central question is when that relaxation already captures the discrete choices exactly.

For a finite simple graph $G=(V,E)$, a vertex cover meets every edge. With nonnegative vertex costs $w_v$, its integer formulation minimizes $\sum_vw_vx_v$ subject to $x_u+x_v\ge1$ for every $uv\in E$ and $x_v\in\{0,1\}$. The standard LP relaxation replaces the binary restriction by $x_v\ge0$. For minimization this can only lower the optimum. Upper bounds $x_v\le1$ may be added without changing the optimal value for nonnegative costs, since clipping any larger coordinate to one preserves all edge constraints.

Its dual packs nonnegative charges on edges:

$$ \min\left\{\sum_vw_vx_v:x_u+x_v\ge1,\ x\ge0\right\},\qquad \max\left\{\sum_ey_e:\sum_{e\ni v}y_e\le w_v,\ y\ge0\right\}. $$

For every feasible pair,

$$ \sum_ey_e\le\sum_{uv\in E}y_{uv}(x_u+x_v) =\sum_vx_v\sum_{e\ni v}y_e\le\sum_vw_vx_v. $$

This is weak duality, an entirely checkable bound. Matching primal and dual objective values certify optimality without trusting a numerical solver's assertion. Strong LP duality guarantees equal optimal values when these finite LPs are feasible and have finite optima; the theorem is a general optimization ingredient, while the inequality proves each certificate used here.

On a triangle with unit costs, $x_v=1/2$ for all three vertices is feasible and has value $3/2$. Assigning $y_e=1/2$ to all three edges is dual feasible with the same value. The LP optimum is therefore exactly $3/2$, but any integer cover needs two vertices. The instance gap, using the minimization convention $\operatorname{OPT}_{\mathrm{IP}}/\operatorname{OPT}_{\mathrm{LP}}$, is $4/3$.

Some matrices prevent fractional vertices. A matrix is totally unimodular when every square subdeterminant is zero, one, or minus one. With an integer right-hand side and nonnegativity constraints, this makes every feasible vertex integral. Bipartite graph incidence matrices and directed network incidence matrices supply important examples. Even then a convex combination of optimal integer vertices may be fractional: the guarantee is existence of an integral optimum, not integrality of every optimal feasible point.

The final investigation also studies a different relaxation. For Max-Cut on a triangle, replace scalar signs $s_v\in\{-1,1\}$ by unit vectors $u_v$, and maximize $\sum_{ij\in E}(1-u_i\cdot u_j)/2$. Scalar signs are included as one-dimensional vectors, so this maximization relaxation gives an upper bound. Three unit vectors separated by $120$ degrees attain $9/4$, while every nontrivial triangle cut has value two. We will prove the relaxed bound with a positive-semidefinite dual certificate. Its gap convention is $\operatorname{OPT}_{\mathrm{SDP}}/\operatorname{OPT}_{\mathrm{cut}}=9/8$.

These definitions, weak duality, and the explicit triangle certificates supply the foundation independently of all optional numbered extensions. Linear algebra helps explain determinants, Gram matrices, and positive semidefiniteness; the prerequisite chapters supply the matching, flow, and matroid objects.

39.1 Linear programming foundations

Optional extension; not required to complete the chapter foundation.

A polyhedron is the intersection of finitely many linear halfspaces; a bounded polyhedron is a polytope. A linear program optimizes a linear functional over such a set. Rational coefficients permit a finite input encoding, but intermediate arithmetic and solution bit lengths still belong in algorithmic complexity claims. In this chapter, the emphasis is exact feasible regions and certificates rather than numerical solver engineering.

A convenient primal–dual pair is

$$ \max\{c^Tx:Ax\le b,\ x\ge0\},\qquad \min\{b^Ty:A^Ty\ge c,\ y\ge0\}. $$

For feasible $x,y$, $c^Tx\le x^TA^Ty=y^TAx\le b^Ty$. The inequality direction changes with the problem's min/max convention. A dual variable prices a primal constraint, but this interpretation does not replace checking its sign and feasibility.

Solved example. Maximize $3x_1+2x_2$ with $x_1+x_2\le4$, $x_1\le2$, $x_2\le3$, and $x\ge0$. The point $(2,2)$ is feasible with value ten. Its dual has constraints $y_1+y_2\ge3$ and $y_1+y_3\ge2$, with objective $4y_1+2y_2+3y_3$. The vector $(2,1,0)$ is feasible and has value ten. Weak duality therefore proves both are optimal.

Complementary slackness describes equality: $y_i(b_i-(Ax)_i)=0$ for each primal constraint, and $x_j((A^Ty)_j-c_j)=0$ for each variable. Here the first two primal constraints are tight; the third has slack one and its price is zero. Both dual variable constraints are tight, consistent with both primal coordinates being positive. These conditions together with feasibility are sufficient for optimality by the equality case of weak duality.

For a nonempty bounded feasible region, an optimal solution exists at a vertex. This does not assert uniqueness: a linear objective may be constant on an entire face. Nor does strong duality assert that an infeasible or unbounded problem has a finite pair of optimal solutions.

Exercise. Check whether $(1,3)$ is optimal in the example, and use the same dual to quantify the difference. Hint: evaluate its objective and the slack in the second constraint. Solution: its value is nine, one below the certified ten. Its first and third constraints are tight, but $x_1\le2$ has slack one with dual price one. This explains the one-unit duality gap at that feasible point.

39.2 Integer programming and integrality

Optional extension; not required to complete the chapter foundation.

The integer hull of a rational polyhedron $P$ is $\operatorname{conv}(P\cap\mathbb Z^n)$. A polyhedron is integral when it equals this integer hull; for a nonempty bounded polyhedron this is equivalent to every vertex being integral. A linear relaxation is exact for a particular objective if its optimum equals the integer optimum. Exactness for one objective is weaker than integrality of the entire feasible region.

For a minimization relaxation with positive LP optimum, define an instance ratio $\operatorname{OPT}_{\mathrm{IP}}/\operatorname{OPT}_{\mathrm{LP}}\ge1$. For a maximization relaxation with positive integer optimum, use $\operatorname{OPT}_{\mathrm{relax}}/\operatorname{OPT}_{\mathrm{IP}}\ge1$. A worst-case integrality gap takes a supremum over a specified family of instances and objectives. Measuring one instance does not determine that supremum. Zero or negative optima require a different convention rather than an undefined ratio.

Exercise. With triangle costs $(1,2,2)$, compare the all-half solution with the best integer cover and give an exact dual certificate for the LP. Hint: use edge charges $y_{ab}=1/2,y_{ac}=1/2,y_{bc}=3/2$. Solution: the fractional cost is $5/2$. The charges satisfy vertex budgets $1,2,2$ and sum to $5/2$, proving LP optimality. The cheapest integer covers are $\{a,b\}$ and $\{a,c\}$, cost three. The ratio is $6/5$, illustrating that a fixed nonintegral polytope can have different gaps for different costs.

39.3 Totally unimodular matrices

Optional extension; not required to complete the chapter foundation.

A matrix $A$ is totally unimodular, abbreviated TU, if every square submatrix has determinant in $\{0,1,-1\}$. The matrix need not be square or have full rank. Integer entries alone are insufficient, and a zero determinant of the full matrix does not prove all its smaller minors have the required values.

If $A$ is TU and $b$ is integral, every vertex of $\{x:Ax\le b,\ x\ge0\}$ is integral. At a vertex, choose enough linearly independent tight constraints, including nonnegativity constraints if needed. Their square coefficient matrix is a nonsingular submatrix of the matrix obtained by appending signed identity rows to $A$. That extension remains TU, so the determinant is $1$ or $-1$. Cramer's rule gives integer coordinates from an integer right-hand side. If a finite optimum is attained at a vertex, an integral optimal solution therefore exists.

A directed vertex–arc incidence matrix places $-1$ at an arc's tail and $+1$ at its head. It is TU. Prove this by induction on the size of a square minor: a column with zero or one nonzero entry permits zero evaluation or expansion to a smaller minor. Otherwise every column has both its opposite entries in the selected rows, so the row sum is zero and the determinant vanishes. This covers every square minor.

Solved example and diagram. Use arcs $e_1:s\to u$, $e_2:u\to t$, and $e_3:s\to t$. In row order $(s,u,t)$ the incidence matrix is

$$ B=\begin{pmatrix}-1&0&-1\\1&-1&0\\0&1&1\end{pmatrix}. $$

It has rank two and is TU. Contrast the unsigned incidence matrix of an undirected triangle, whose determinant is two. The diagram fixes both edge orders and every matrix entry. An underlying triangle does not spoil the directed-incidence theorem: signed and unsigned incidence are different matrices.

For a bipartite graph, multiplying the unsigned incidence rows in one bipartition by $-1$ produces a signed incidence matrix. Row sign changes preserve minor magnitudes, so the unsigned bipartite matrix is TU. Transposition and multiplication by $-1$ also preserve TU. This applies to both degree-constrained bipartite matching and its cover dual. On the triangle, no bipartition can put opposite signs at both endpoints of every edge.

Exercise. Why is an integer right-hand side essential? Hint: use a one-variable TU matrix. Solution: $0\le x\le1/2$ has coefficient matrix consisting of $1$ and $-1$, which is TU, but its right-hand side includes $1/2$. The vertex $x=1/2$ is fractional. TU controls the denominator from the matrix, not arbitrary fractional data on the right.

39.4 Linear-programming duality and min-max theorems

Optional extension; not required to complete the chapter foundation.

A min-max theorem can arise by combining strong LP duality with integrality on both sides. For a bipartite graph, the fractional matching LP maximizes $\sum_ex_e$ with $\sum_{e\ni v}x_e\le1$ and $x\ge0$. Its dual minimizes $\sum_vz_v$ with $z_u+z_v\ge1$ for every edge and $z\ge0$. TU permits integral optimal solutions. Integral matching solutions select disjoint edges, and an integral cover optimum can be clipped to zero–one. Consequently maximum matching size equals minimum vertex-cover size: König's theorem.

The inequality direction is immediate even without LP machinery: each matching edge needs a distinct vertex in any cover. Strong duality and integrality prove that this bound can be attained for bipartite graphs. In nonbipartite graphs, the same fractional LP duality still holds, but those integer interpretations may fail.

Solved example. On the path $a-b-c-d$, the matching $\{ab,cd\}$ has size two and the cover $\{b,c\}$ has size two. These objects certify each other's optimality. As LP vectors, put one on the two matching edges and one on the two cover vertices. Every constraint is feasible, and the values match. Complementary slackness is visible: both selected cover vertices are incident to total matching weight one, and each selected matching edge has total cover weight one.

On the triangle, maximum matching size is one while minimum cover size is two. The fractional matching and cover optima are both $3/2$. The min-max equality has not failed at the LP level; integrality has failed when translating its fractional solutions back into those particular combinatorial objects.

Proof mechanism; omitted prerequisite. Strong LP duality can be proved using a separating-hyperplane or alternative theorem. Its full general proof is omitted. Every finite optimality claim in these worked examples is established directly by feasible matching-value certificates, so none depends on an unchecked solver result.

Exercise. Give a matching and a minimum cover for the star with three leaves. Hint: one center touches every edge. Solution: any one edge is a matching of size one; the center alone is a cover of size one. They attain the weak bound and certify optimality.

39.5 Matching, flow, and cut polyhedra

Optional extension; not required to complete the chapter foundation.

A matching polytope is the convex hull of matching incidence vectors. In a general graph, nonnegativity and vertex-degree inequalities need strengthening. Edmonds' matching-polytope theorem includes, for every odd vertex subset $S$, the inequality

$$ \sum_{e\in E(S)}x_e\le\frac{|S|-1}{2}. $$

A matching uses an even number of vertices inside $S$ through internal edges, so this inequality is valid. Together with degree constraints and nonnegativity, these odd-set inequalities describe the matching polytope. The full sufficiency theorem is stated rather than proved here. On a triangle, the inequality is $x_{ab}+x_{bc}+x_{ca}\le1$, excluding the all-half fractional matching.

For directed flows, use the signed incidence convention from Section 39.3. Feasibility is $Bf=b$, $0\le f\le u$, where $b$ records net inflow and $u$ arc capacities. Integer capacities and supplies yield integral vertices through the TU incidence structure and bound rows. The box bounds make a finite-capacity flow polytope bounded. A general network with unconstrained circulation directions need not be bounded.

Solved flow-and-cut certificate. Take capacities $u_{sa}=2$, $u_{at}=1$, $u_{sb}=1$, $u_{bt}=2$, and $u_{ab}=1$. A feasible flow sends two on $sa$, one on $at$, one on $ab$, one on $sb$, and two on $bt$. Conservation holds at $a,b$, and the flow value is three. The cut with source side $\{s\}$ has capacity $2+1=3$. Every flow value is at most every source–sink cut capacity, so both are optimal. The integer flow is the actual object, while the cut is its upper-bound certificate.

A source–sink cut vector records arcs leaving a vertex set containing $s$ but not $t$; the cut polytope is their convex hull. Minimum source–sink cut has a flow dual interpretation, but arbitrary cut optimization does not inherit the same integrality argument. In particular, Max-Cut has a distinct relaxation studied below. The word “cut” alone does not identify a TU formulation.

Exercise. If the arc $a\to b$ is deleted in the example, find the new maximum flow and a certifying cut. Hint: isolate the two direct two-arc routes. Solution: each route carries at most one, so a flow of value two is feasible. The source side $\{s,a\}$ has outgoing capacity one on $at$ and one on $sb$, totaling two. This cut proves the new optimum.

39.6 Submodular functions and optimization

Optional extension; not required to complete the chapter foundation.

A set function $F:2^V\to\mathbb R$ is submodular if

$$ F(A)+F(B)\ge F(A\cup B)+F(A\cap B) $$

for all $A,B$. Equivalently, its marginal gains diminish: if $A\subseteq B$ and $v\notin B$, then $F(A\cup\{v\})-F(A)\ge F(B\cup\{v\})-F(B)$. Monotone means $F(A)\le F(B)$ under inclusion, and normalized means $F(\varnothing)=0$.

Coverage is a concrete example. Assign a feature set $T_v$ to each item and let $F(S)=|\bigcup_{v\in S}T_v|$. Adding $v$ gains features in $T_v$ not yet covered; a larger current set leaves fewer new features, proving diminishing returns. Matroid rank is another submodular function, while nonnegative-weight graph cut functions are submodular but generally not monotone.

Solved example. Use items $a,b,c$ covering $T_a=\{1,2,3,4\}$, $T_b=\{1,2,5\}$, and $T_c=\{3,4,6\}$, with a budget of two items. Greedy chooses $a$ first because its value four exceeds the other singleton values three. Each remaining item then has marginal gain one; breaking the tie toward $b$ gives value five. Choosing $b,c$ covers all six features, so the optimum is six. Submodularity does not make this greedy choice exact.

For normalized monotone submodular maximization under $|S|\le k$, greedy has the proved guarantee

$$ F(S_k)\ge\left(1-(1-1/k)^k\right)\operatorname{OPT}\ge(1-1/e)\operatorname{OPT},\qquad k\ge1. $$

At step $i$, submodularity and monotonicity give $\operatorname{OPT}-F(S_i)\le\sum_{v\in S^{\ast}\setminus S_i}\Delta(v\mid S_i)\le k\max_v\Delta(v\mid S_i)$. Hence greedy reduces the remaining deficit by at least a $1/k$ fraction. Iterating proves the displayed bound. With $k=2$, the finite-step guarantee is $3/4$; the example's ratio $5/6$ respects it. This is the classical Nemhauser–Wolsey–Fisher theorem.

Unconstrained submodular minimization has polynomial-time value-oracle algorithms; an established strongly polynomial oracle result is Schrijver's algorithm. This is a different task from constrained monotone maximization. Oracle-call bounds presume access to exact values at a stated cost; they do not make a computationally expensive function evaluator free.

Exercise. Compute the marginal value of $b$ at the empty set and at $\{a\}$. Hint: count newly covered features. Solution: the gains are three and one, respectively. At $\{a,c\}$ the gain is also one, from feature five. These values exhibit diminishing returns without requiring every comparison to be strict.

39.7 Greedy optimization over matroids

Optional extension; not required to complete the chapter foundation.

For a matroid $M=(E,\mathcal I)$ with rank function $r$, maximizing a nonnegative linear weight over independent sets is solved exactly by sorting elements in nonincreasing weight order and adding each when independence is preserved. This is a modular objective, $w(S)=\sum_{e\in S}w_e$, rather than the general submodular coverage objective above.

Here is a compact proof. Write the sorted weights as $w_1\ge\cdots\ge w_n\ge0$ and set $w_{n+1}=0$. After processing a prefix $[i]$, greedy has a maximal independent subset of that prefix, hence has size $r([i])$ there. For any independent $I$, $|I\cap[i]|\le r([i])$. The identity

$$ w(I)=\sum_{i=1}^n(w_i-w_{i+1})|I\cap[i]| $$

then implies $w(I)\le\sum_i(w_i-w_{i+1})r([i])=w(G)$. Nonnegative differences make every inequality valid. The matroid augmentation property is what ensures maximal independent prefix sets have maximum size.

The associated independence polytope is $\{x\ge0:x(S)\le r(S)\text{ for all }S\subseteq E\}$, where $x(S)=\sum_{e\in S}x_e$. Its vertices are independent-set incidence vectors, an established matroid-polytope theorem. Exponentially many written inequalities do not mean a given optimization method must inspect all of them. Greedy uses sorting plus one independence-oracle call per element; its cost is $O(n\log n)$ comparisons and $n$ oracle calls, with oracle implementation costs additional.

Solved example. In the graphic matroid of a triangle, give edge weights five, four, and one. Independent sets are forests. Greedy selects the five- and four-weight edges, then rejects the final edge because it creates a cycle. The weight is nine; the other spanning trees have weights six and five. The rank-prefix proof explains why the local cycle test yields a globally maximum forest here.

If weights can be negative and arbitrary independent sets are allowed, omit negative-weight elements. For a prescribed basis, negative weights cannot simply be omitted: the fixed cardinality requirement changes the task. Objective and feasibility assumptions must remain explicit.

Exercise. Why can the coverage greedy example be suboptimal without contradicting matroid greedy optimality? Hint: distinguish the objective functions. Solution: a cardinality limit is a uniform-matroid constraint, but coverage is submodular and nonlinear in selected items. Matroid greedy's exact theorem applies to sums of fixed element weights. An item's coverage marginal changes with the selected set, so that theorem does not apply.

39.8 Approximation algorithms

Optional extension; not required to complete the chapter foundation.

For minimization, an approximation factor $\rho\ge1$ means a feasible output of cost at most $\rho\operatorname{OPT}$. For maximization, a factor $\alpha\le1$ means value at least $\alpha\operatorname{OPT}$. Expected-value guarantees for randomized algorithms must be labeled as expectations, rather than promises about every run.

For weighted vertex cover with nonnegative costs, solve the standard LP and select all vertices with $x_v\ge1/2$. Every edge has an endpoint meeting that threshold because its endpoints sum to at least one. The rounded cover is feasible and

$$ \sum_{v:x_v\ge1/2}w_v\le2\sum_vw_vx_v =2\operatorname{OPT}_{\mathrm{LP}}\le2\operatorname{OPT}_{\mathrm{IP}}. $$

This proves a factor-two guarantee. Feasibility and cost comparison are both needed: a cheap rounded vector leaving an edge uncovered is not an approximation solution. The statement assumes an optimal LP solution; certified approximate solutions require accounting for their error.

Solved example. On the unit-cost triangle, the all-half optimum rounds to all three vertices, costing three. The integer optimum is two, so this instance's approximation ratio is $3/2$, below the proved worst-case bound two. The ratio against the LP is $3/(3/2)=2$. These two comparisons answer different questions: rounding loss relative to the relaxation and final loss relative to the discrete optimum.

For an unweighted graph, taking both endpoints of a maximal matching also gives a factor-two cover. If an uncovered edge had both endpoints outside the chosen set, it could be added to the matching, contradicting maximality. A matching of size $m$ gives a lower bound $m$ on every cover, while the output has size $2m$. Maximal means not extendable by another edge; maximum means globally largest cardinality. The approximation proof needs only maximality.

Exercise. On the path $a-b-c-d$, compare the cover obtained from maximal matching $\{bc\}$ with that from maximum matching $\{ab,cd\}$. Hint: take all endpoints. Solution: the first gives $\{b,c\}$ of cost two, which is optimal; the second gives all four vertices of cost four, ratio two. A stronger lower-bound matching does not automatically make this particular endpoint-rounding output smaller.

39.9 Primal-dual approximation methods

Optional extension; not required to complete the chapter foundation.

Primal-dual algorithms construct a feasible combinatorial solution while growing a feasible dual certificate. They need not solve the LP to optimality. For weighted vertex cover, attach nonnegative edge charges $y_e$ with budgets $\sum_{e\ni v}y_e\le w_v$. A vertex is tight when equality holds.

Initially all charges are zero, and select every zero-cost vertex. While an uncovered edge $uv$ remains, raise its charge until one endpoint exhausts its remaining budget. Select every endpoint that becomes tight. The raising amount is the smaller of the two budget slacks. Existing selected vertices cannot be incident to an uncovered edge, so later charge increases never violate their budgets or change their tightness. At least one new vertex is selected at each step, ensuring termination.

Every selected vertex is tight, and the final set $C$ covers all edges. Therefore

$$ w(C)=\sum_{v\in C}\sum_{e\ni v}y_e =\sum_ey_e|e\cap C|\le2\sum_ey_e\le2\operatorname{OPT}_{\mathrm{IP}}. $$

The last inequality is weak duality. The factor two comes from each edge charge being paid at most twice, not from a claim that the constructed dual is optimal. With rational costs, exact slack calculations provide a checkable rational certificate.

Solved example. On the unit-cost triangle, choose edge $ab$ and raise $y_{ab}$ to one. Both endpoints become tight and are selected. All three edges are then covered, so the algorithm stops with cost two. The dual has value one, giving the factor-two bound exactly. Yet the LP-optimal dual has value $3/2$. Thus a nonoptimal dual can certify a valid approximation; a matching primal/dual certificate would be needed to certify LP optimality.

For weighted path $a-b-c$ with costs $(2,1,2)$, raising the charge on $ab$ to one makes only $b$ tight. Selecting it covers both edges, with primal cost one and dual value one. Here the algorithm happens to produce an exact optimality certificate.

Exercise. Why must zero-cost vertices be handled before raising charges? Hint: their feasible slack is already zero. Solution: they are tight at initialization and can be selected freely. Otherwise choosing an uncovered edge incident to one would permit no positive increase, and an implementation that waits for a positive raise could stall. Selecting all such vertices preserves both feasibility and the cost proof.

39.10 Semidefinite programming and combinatorial relaxations

Optional extension; not required to complete the chapter foundation.

A real symmetric matrix $X$ is positive semidefinite, written $X\succeq0$, when $z^TXz\ge0$ for every real vector $z$. Equivalently it is a Gram matrix, $X_{ij}=u_i\cdot u_j$, of real vectors. The constraints $X_{ii}=1$ make those vectors unit length. A semidefinite program optimizes a linear matrix functional over linear constraints and this positive-semidefinite cone.

For a graph with nonnegative edge weights $w_{ij}$, scalar signs encode a cut: edge $ij$ crosses when $s_is_j=-1$. Its objective is $\sum_{ij}w_{ij}(1-s_is_j)/2$. Let $L$ be the weighted graph Laplacian, with diagonal weighted degrees and off-diagonal entries $-w_{ij}$. The SDP relaxation and its dual are

$$ \max\left\{\tfrac14\langle L,X\rangle:X\succeq0,\ X_{ii}=1\right\},\qquad \min\left\{\sum_i y_i:\operatorname{Diag}(y)-L/4\succeq0\right\}, $$

where $\langle A,B\rangle=\operatorname{tr}(A^TB)$ and the dual coordinates $y_i$ are unrestricted in sign. For feasible matrices, the inner product of two positive-semidefinite matrices is nonnegative. Thus

$$ \tfrac14\langle L,X\rangle\le\langle\operatorname{Diag}(y),X\rangle=\sum_i y_i, $$

providing weak SDP duality. The sign vectors produce rank-one feasible matrices $ss^T$, so the relaxation bounds the integer optimum from above.

Solved example. For the unit-weight triangle, take $X$ with diagonal one and every off-diagonal entry $-1/2$. It is the Gram matrix of three unit vectors at $120$ degrees and has eigenvalues $3/2,3/2,0$, so it is feasible. Its objective is $3(1+1/2)/2=9/4$. Let $y_i=3/4$ for all vertices. Since the triangle Laplacian has diagonal two and off-diagonal minus one,

$$ \operatorname{Diag}(y)-L/4=J/4\succeq0, $$

where $J$ is the all-ones matrix. The dual value is $9/4$, proving exact SDP optimality. The integer optimum is two, so the instance gap is $9/8$.

Random hyperplane rounding chooses a rotationally invariant random direction and assigns a vertex by the sign of its dot product with its vector. Vectors at angle $\theta$ are separated with probability $\theta/\pi$. Comparing this with their SDP contribution $(1-\cos\theta)/2$ yields the established expected approximation factor

$$ \alpha_{\mathrm{GW}}=\min_{0\lt\theta\le\pi}\frac{2\theta}{\pi(1-\cos\theta)}\approx0.87856. $$

For nonnegative weights, summing edgewise gives expected cut value at least $\alpha_{\mathrm{GW}}$ times the SDP value, and hence at least that factor times the integer optimum. This is the classical Goemans–Williamson result (1995), not a claim about a best current algorithm or conjectural hardness threshold. A feasible SDP solution within additive error $\varepsilon$ of the optimum gives the corresponding guarantee $\alpha_{\mathrm{GW}}(\operatorname{OPT}_{\mathrm{SDP}}-\varepsilon)$; numerical feasibility and precision require their own treatment.

Exercise. Compute the expected rounded cut value for the three $120$-degree vectors. Hint: every edge has separation probability $2/3$. Solution: the expectation is $3\cdot2/3=2$. Relative to the SDP value it is $8/9$, and relative to the integer optimum it is one. In fact, except for measure-zero boundary directions, the rounding always produces a nontrivial triangle cut of value two. The general expected guarantee need not be tight on this example.

Derive a dual certificate and measure a relaxation's integrality gap

The investigation produces exact certificates for both an LP and an SDP. It makes the LP-foundation/semidefinite connection through the same weak-duality principle: every feasible dual object bounds every feasible primal object. The feasible cones and integer encodings differ, so numerical gaps must be reported with their objective directions and denominators.

Worked solution: integer optima. The feasible binary cover vectors are $110,101,011,111$, with minimum cost two. The four smaller-cardinality vectors fail at least one edge constraint. For Max-Cut, the two constant sign vectors have value zero and the other six have value two. Complementary sign vectors yield identical edge-crossing patterns, giving four cuts up to that symmetry. Thus the integer cut optimum is exactly two.

Worked solution: LP and path comparison. For the triangle, $x=(1/2,1/2,1/2)$ satisfies all three edge constraints at equality. Edge charges $y=(1/2,1/2,1/2)$ meet all three unit budgets at equality. Both objectives are $3/2$, and weak duality proves LP optimality. The tight matrix has determinant two and unique solution the all-half vector, so this is a fractional vertex. The minimization instance ratio is $2/(3/2)=4/3$.

For the path, $x_b=x_c=1$ and all other coordinates zero form a cover of value two. Charges one on $ab,cd$ and zero on $bc$ are dual feasible with value two. Therefore the LP and integer optima coincide. The all-half feasible point is the midpoint of the distinct covers $\{a,c\}$ and $\{b,d\}$, so it is not a vertex. An integral polytope contains fractional convex combinations; its vertices, rather than every contained point, are integral. Exact enumeration of the directed $3\times3$ matrix's minors gives only zero and signed ones, agreeing with the general incidence-matrix proof.

Worked solution: SDP. The matrix $X=(3/2)I-(1/2)J$ acts as zero on the all-ones vector and as multiplication by $3/2$ on its perpendicular two-dimensional subspace. Thus it is PSD and has unit diagonal. Its objective is $9/4$. The choice $y=(3/4,3/4,3/4)$ gives slack $J/4$, whose quadratic form is $(\sum_i z_i)^2/4\ge0$. Therefore the dual is feasible with equal value, proving optimality by weak SDP duality alone.

The maximization gap is $(9/4)/2=9/8$. Hyperplane rounding separates each pair with probability $2/3$, giving expected value two. The LP cover gap and SDP cut gap are different instance measurements of different relaxations, despite using the same underlying triangle. Neither number alone is the supremum gap over all graphs.

Worked solution: exact exploration. The triangle's nonnegative cover polyhedron has four vertices: $110,101,011$ and $(1/2,1/2,1/2)$. To reproduce this list, select three linearly independent tight constraints from the three edge inequalities and three nonnegativity inequalities, solve the resulting system over the rationals, reject infeasible candidates, and deduplicate. The vector $111$ is feasible but not a vertex: none of its edge or nonnegativity inequalities is tight. The polyhedron is unbounded upward; this does not prevent its positive-cost minimum from being attained at one of the listed vertices.

A hyperplane simulation can sample a uniform angle for the planar $120$-degree Gram vectors and record the resulting cuts. Excluding directions exactly perpendicular to a vector, every sampled cut has value two: all three dot products cannot have the same strict sign because the vectors sum to zero. This exact fact explains the simulated observation; merely obtaining an empirical mean close to two would not establish the general Goemans–Williamson guarantee.

Application and extension. A cover can represent placing monitors at network nodes so that every link has a monitored endpoint. An LP dual distributes feasible link charges and certifies a lower bound on monitoring cost; a rounded or primal-dual cover supplies an implementable plan. Max-Cut can model splitting conflicting interactions into two groups, with its SDP supplying an upper bound and rounding producing a feasible partition. Additional capacities, reliability assumptions, or different objectives require a corresponding model; the certificates apply to the precise formulations stated here.

With costs $(1,2,2)$, the all-half cover has value $5/2$, and charges $(y_{ab},y_{ac},y_{bc})=(1/2,1/2,3/2)$ certify that optimum. The best integer cover has cost three, so its ratio is $6/5$. Adding $x_a+x_b+x_c\ge2$ makes the minimum three for these costs: the objective is $2(x_a+x_b+x_c)-x_a$, and if $x_a\le1$ it is at least three; if $x_a\ge1$, the edge constraint $x_b+x_c\ge1$ gives objective at least $x_a+2\ge3$. The feasible cover $\{a,b\}$ attains three. For unit costs the added inequality similarly raises the LP optimum to two, eliminating the observed triangle gap.