Approximation Algorithms and Gap Reductions: Examples and Counterexamples

The cover $\{S_1,S_2\}$ has cost $2+2=4$. Every cover containing $S_3$ costs at least $5$, since costs are nonnegative; every cover not containing $S_3$ must contain $S_1$ to cover element $1$ and $S_2$ to cover element $3$, hence costs at least $4$. Therefore the minimum cover cost is $\mathrm{O}\mathrm{P}\mathrm{T}=4$.

Initially all four elements are uncovered, so $r=4$ and the ratios are $2\mathrm{/}2=1$ for $S_1$, $2\mathrm{/}2=1$ for $S_2$ and $5\mathrm{/}4$ for $S_3$; the minimum $1$ is attained by both $S_1$ and $S_2$, and the input-order tie rule selects $S_1$, which charges $2\mathrm{/}2=1$ to each of the elements $1$ and $2$. With $r=2$ elements $\{3,4\}$ uncovered, the ratios are $2\mathrm{/}2=1$ for $S_2$ and $5\mathrm{/}2$ for $S_3$; the algorithm selects $S_2$ and charges $1$ to each of $3$ and $4$. The uncovered set is then empty, so the algorithm stops with cover $\{S_1,S_2\}$ of total cost $4=\mathrm{O}\mathrm{P}\mathrm{T}$.

At the first round $r=4$ and the chosen price $1$ satisfies $1\le \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}4=1$; at the second round $r=2$ and $1\le \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}2=2$. Ordering the elements by first coverage, ties by input order, gives $1,2,3,4$, so the four charges are all $1$ and satisfy $1\le \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(4-j+1)$ for $j=1,2,3,4$, namely $1\le 4\mathrm{/}4$, $1\le 4\mathrm{/}3$, $1\le 4\mathrm{/}2$, $1\le 4\mathrm{/}1$; the first of these is an equality and the other three are strict. The sum of the charges is $4\le H_4\mathrm{O}\mathrm{P}\mathrm{T}=(25\mathrm{/}12)\cdot 4=25\mathrm{/}3$ by [F3].

Thus the total greedy cost here equals the optimum $4$, the pointwise charge bound of [F2] holds at each element with the remaining count actually in force, and the harmonic bound $H_4\mathrm{O}\mathrm{P}\mathrm{T}=25\mathrm{/}3$ is strictly larger than both the greedy cost and the optimum; the example also shows the two bound forms at work: the per-round bound $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$ uses the remaining count $r$ of that round, while the per-element bound $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)$ is the index-based consequence.

Take the instance map $f(F):=G_F$ of [F1], which runs in polynomial time and produces a finite simple graph whose independent sets have value ${\mathrm{val}}_{\mathrm{\Gamma }}(I)=\mathrm{\mid }I\mathrm{\mid }$. Take the decoder $g(F,I)$ of [F1], which from every independent set $I$ of $G_F$ produces in polynomial time an assignment of $F$ satisfying at least $\mathrm{\mid }I\mathrm{\mid }$ clauses, of value ${\mathrm{val}}_{\mathrm{\Pi }}(g(F,I))$ equal to its satisfied-clause count. Both objectives are maximization with nonnegative values by [F4].

The first L-reduction inequality holds with $a=1$: by the exact optimum equality of [F1], ${\mathrm{OPT}}_{\mathrm{\Gamma }}(f(F))=\alpha (G_F)={\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)=1\cdot {\mathrm{OPT}}_{\mathrm{\Pi }}(F)$ for every 3-CNF formula $F$ with three literal occurrences per clause.

The second L-reduction inequality holds with $b=1$: writing $t:={\mathrm{val}}_{\mathrm{\Pi }}(g(F,I))$ for the number of clauses satisfied by the decoded assignment, [F1] gives $t\ge \mathrm{\mid }I\mathrm{\mid }$, and therefore $\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Pi }}(F)-{\mathrm{val}}_{\mathrm{\Pi }}(g(F,I))\mathrm{\mid }={\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)-t\le {\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)-\mathrm{\mid }I\mathrm{\mid }=\alpha (G_F)-\mathrm{\mid }I\mathrm{\mid }=\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Gamma }}(f(F))-{\mathrm{val}}_{\mathrm{\Gamma }}(I)\mathrm{\mid }$, where the last step uses ${\mathrm{val}}_{\mathrm{\Gamma }}(I)=\mathrm{\mid }I\mathrm{\mid }$ and step 2.1.

Steps 2.1 and 3.1 exhibit the maps and constants required by [F2], so $(f,g,1,1)$ is an L-reduction from Max-3SAT to maximum independent set. By the transfer statement [F3], a feasible independent set with relative error at most $ϵ$, that is ${\mathrm{val}}_{\mathrm{\Gamma }}(I)\ge (1-ϵ)\alpha (G_F)$, decodes to a Max-3SAT assignment with relative error at most $1\cdot 1\cdot ϵ=ϵ$; when $\alpha (G_F)=0$ the decoded assignment is optimal.

A concrete formula is $F=(x\vee x\vee x)\wedge (\mathrm{\neg }x\vee \mathrm{\neg }x\vee \mathrm{\neg }x)$ with $m=2$ clauses of three literal occurrences. No assignment satisfies both clauses: $x$ true satisfies only the first and $x$ false satisfies only the second, so ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)=1$. The graph $G_F$ has $6$ vertices in two clause clusters of three; an independent set takes at most one vertex per cluster, and every vertex of the first cluster is complementary to every vertex of the second, so no independent set has size $2$, while a single vertex is independent; hence $\alpha (G_F)=1={\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F)$, and an independent set of size $1$ decodes to an assignment satisfying at least $1$ clause.

The explicit clause-literal construction therefore is an L-reduction with constants $a=b=1$: the optimum values agree, and every independent set of size $k$ decodes to an assignment satisfying at least $k$ clauses, so errors transfer unchanged and an independent-set approximation ratio carries over to Max-3SAT with the same relative error.

Minimum vertex cover has NP-hard exact optimization: by [F2] its threshold problem is NP-complete, so a polynomial-time exact optimizer would decide an NP-complete problem and imply $P=NP$. Yet [F3] gives a deterministic polynomial-time algorithm that always returns a vertex cover of size at most $2{\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$. Thus the existence of a constant-factor approximation is compatible with exact NP-hardness and refutes the unqualified claim of [F1]; it does not establish or refute a lower bound conditioned on $P\mathrm{\ne }NP$.

The four-vertex path $P_4$ with vertices $v_1,v_2,v_3,v_4$ and edges $v_1{v}_2,v_2{v}_3,v_3{v}_4$ exhibits the two matchings. The single edge $v_2{v}_3$ is a maximal matching whose endpoint set $\{v_2,v_3\}$ is a vertex cover: it meets $v_1{v}_2$ at $v_2$, $v_2{v}_3$ itself, and $v_3{v}_4$ at $v_3$. One vertex meets at most two of the three edges, so no cover of size one exists and ${\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}(P_4)=2$; the matching lower bound is $\mathrm{\mid }M\mathrm{\mid }=1\le 2$. Scanning edges in the order $v_1{v}_2,v_2{v}_3,v_3{v}_4$ instead inserts the disjoint outer edges $v_1{v}_2$ and $v_3{v}_4$, a maximal matching whose endpoint set is all of $V$ with $\mathrm{\mid }C\mathrm{\mid }=4=2\cdot {\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}(P_4)$, realizing the factor-two upper bound on this graph.

Minimum vertex cover has NP-hard exact optimization and a polynomial-time factor-two approximation by step 1.1, so it refutes the unqualified claim of [F1]. The path in step 2.1 illustrates the tightness of the factor but does not establish the uniform ratio; that is the content of the general theorem in [F3]. A conditional claim that approximation is impossible unless $P=NP$ is not refuted here.

For $K_3$ the edge set has $m=3$ elements, so by [F1] the initial conditional expectation over no fixed bits is the expected cut size $m\mathrm{/}2=3\mathrm{/}2$; the algorithm of [F2] now fixes $b_1,b_2,b_3$ in order.

At the first step every one of the three edges has at least one unfixed endpoint, so each contributes $1\mathrm{/}2$ to both candidates for $b_1$ and both conditional expectations equal $3\mathrm{/}2$; the tie rule of [F2] selects $b_1=0$. With $b_1=0$ fixed, the candidate $b_2=0$ finishes the edge $v_1{v}_2$ as non-crossing and leaves $v_2{v}_3$ and $v_1{v}_3$ with an unfixed endpoint each, giving conditional expectation $0+\frac{1}{2}+\frac{1}{2}=1$, while the candidate $b_2=1$ makes $v_1{v}_2$ crossing and again leaves the other two edges half-crossing, giving $1+\frac{1}{2}+\frac{1}{2}=2$; since $2>1$ the algorithm fixes $b_2=1$.

With $b_1=0$ and $b_2=1$ fixed, the candidate $b_3=0$ gives crossing edges $v_1{v}_2$ and $v_2{v}_3$ but not $v_1{v}_3$, a cut size of $2$, and the candidate $b_3=1$ gives crossing edges $v_1{v}_2$ and $v_1{v}_3$ but not $v_2{v}_3$, also a cut size of $2$; both conditional expectations equal the actual final cut size because every edge is then finished, and the tie rule fixes $b_3=0$.

The returned placement $(b_1,b_2,b_3)=(0,1,0)$ has cut $\{v_1,v_3\}$ against $\{v_2\}$ with crossing edges $v_1{v}_2$ and $v_2{v}_3$, so its cut size is $2\ge 3\mathrm{/}2=m\mathrm{/}2$, and this equals ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}(K_3)=2$, since a triangle placement crosses at most two of its three edges and the displayed cut crosses exactly two. The instance therefore realizes the conditional-expectation guarantee with the initial expectation $3\mathrm{/}2$.

The six stated distances are nonnegative and symmetric with $d(u,u)=0$; every distance between distinct vertices is $1$ or $2$, so for any three vertices with $u\mathrm{\ne }v\mathrm{\ne }w$ one has $d(u,v)+d(v,w)\ge 1+1=2\ge d(u,w)$, and inserting $v=u$ or $v=w$ gives the equality $d(u,w)=d(u,v)+d(v,w)$. The triangle inequality therefore holds and the data form a metric-TSP instance on four vertices.

The edge set $T=\{AB,BC,CD\}$ has $4$ vertices, $3$ edges, and forms the path $A-B-C-D$, hence is connected and acyclic, a spanning tree; its weight is $w(T)=1+1+1=3$. Every spanning tree of a four-vertex graph has exactly $3$ edges by [F2] and every edge length is at least $1$, so every spanning tree has weight at least $3$; therefore $T$ is a minimum spanning tree and $w(T)=3$.

Every tour is a cyclic ordering of the four vertices and consists of four edges, each of length at least $1$, so every tour has cost at least $4$; the cyclic ordering $A-B-C-D-A$ has cost $1+1+1+1=4$. Hence ${\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}=4$.

Doubling the three tree edges produces the multigraph with edges $AB,BA,BC,CB,CD,DC$; it is connected and the degrees are $\mathrm{deg}(A)=2$, $\mathrm{deg}(B)=4$, $\mathrm{deg}(C)=4$, $\mathrm{deg}(D)=2$, all even. The closed walk $A-B-C-D-C-B-A$ uses each of the six edges exactly once, so it is an Euler circuit of the doubled multigraph, with total cost $1+1+1+1+1+1=6=2w(T)$.

The vertices occur for the first time along this walk in the order $A,B,C,D$, so first-visit shortcutting yields the tour $A-B-C-D-A$. Its segments are the walks $A\to B$, $B\to C$, $C\to D$ of length $1$ each and the return segment $D\to C\to B\to A$ of length $3$; the shortcut edge $DA$ has length $1\le 3$, the sum of the segment lengths, so the shortcut tour has cost $1+1+1+1=4\le 6=2w(T)$, and by step 2.2 it equals ${\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$.

The computed tree satisfies $w(T)=3\le 4={\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$, in agreement with the minimum-spanning-tree lower bound, and the shortcut tour has cost $4\le 6=2w(T)\le 2{\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}=8$, so this instance realizes the double-tree guarantee of [F4] with a strict improvement over the doubled walk.