Approximation: How Close Is a Feasible Answer?
Many graph optimization problems ask for the best feasible object: a smallest vertex cover, a largest cut, or a largest independent set. Finding an optimum may be computationally difficult, so an algorithm may instead return a feasible answer that is close to the optimum. Approximation ratios give a precise multiplicative way to describe that closeness.
A ratio has to be interpreted in light of whether the objective is minimized or maximized. A larger value is worse for minimization but better for maximization. We will use three graph problems to make that distinction concrete, while keeping separate two questions that are often confused: how well an algorithm does on one particular graph, and what it guarantees on every input.
For a fixed input, let \(\mathrm{OPT}\) denote the objective value of an optimal solution, and let \(\mathrm{ALG}\) denote the value of the solution returned by an algorithm. For a minimization problem, \(\mathrm{ALG}\ge\mathrm{OPT}\); for a maximization problem, \(\mathrm{ALG}\le\mathrm{OPT}\). These inequalities follow because \(\mathrm{OPT}\) is, respectively, the minimum or maximum over all feasible solutions.
Two Conventions for Ratios
For minimization, the approximation ratio on an input with \(\mathrm{OPT}>0\) is \(\mathrm{ALG}/\mathrm{OPT}\). It is at least \(1\), and a smaller value is better. An algorithm has a factor-\(\rho\) guarantee, where \(\rho\ge1\), if on every input in the stated domain it returns a feasible solution satisfying \(\mathrm{ALG}\le \rho\,\mathrm{OPT}\).
For maximization with \(\mathrm{OPT}>0\), a common convention is to state an \(\alpha\)-approximation guarantee, where \(0<\alpha\le1\): the algorithm must satisfy \(\mathrm{ALG}\ge\alpha\,\mathrm{OPT}\) on every input in its domain. Equivalently, the reciprocal ratio \(\mathrm{OPT}/\mathrm{ALG}\) is at most \(1/\alpha\) whenever \(\mathrm{ALG}>0\). Thus a larger \(\alpha\) is better, whereas a smaller factor \(\rho\) is better.
Proof. In a minimization problem, the ratio is defined as \(\mathrm{ALG}/\mathrm{OPT}\). Since \(\mathrm{OPT}>0\), multiplying \(\mathrm{ALG}/\mathrm{OPT}\le\rho\) by \(\mathrm{OPT}\) gives \(\mathrm{ALG}\le\rho\,\mathrm{OPT}\), and dividing that inequality by \(\mathrm{OPT}\) gives the reverse implication. In a maximization problem, \(\mathrm{OPT}>0\), so dividing \(\mathrm{ALG}\ge\alpha\,\mathrm{OPT}\) by \(\mathrm{OPT}\) gives \(\mathrm{ALG}/\mathrm{OPT}\ge\alpha\), and multiplication reverses this step. If \(\mathrm{ALG}>0\), taking reciprocals of the positive quantities in the last inequality gives \(\mathrm{OPT}/\mathrm{ALG}\le1/\alpha\); taking reciprocals again gives the converse. \(\square\)
A guarantee is a statement about all inputs in the algorithm’s domain, not just the graph used in an example. If an algorithm is randomized, a guarantee must also specify how randomness is treated, such as an expectation or a probability of success; here we discuss deterministic guarantees. Ratios also require care when the optimum is zero. The quotient \(\mathrm{ALG}/\mathrm{OPT}\) is undefined at zero. One must either restrict the ratio statement to positive-optimum inputs or state the guarantee as an inequality and separately handle zero-optimum cases.
Worked Examples on Graphs
Worked Example: Vertex Cover on a Five-Vertex Graph
A vertex cover is a set of vertices containing at least one endpoint of every edge. Consider the simple graph \(G=(V,E)\) with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,13,34,45\}\). Suppose an algorithm returns \(C=\{1,2,4,5\}\).
Check feasibility edge by edge: \(12\) meets \(C\) at \(1\) and \(2\); \(23\) at \(2\); \(13\) at \(1\); \(34\) at \(4\); and \(45\) at \(4\) and \(5\). Thus \(C\) is a cover and \(\mathrm{ALG}=|C|=4\).
To find the optimum, edges \(12,23,13\) form a triangle, and covering all three requires at least two vertices from \(\{1,2,3\}\): selecting at most one would leave the edge between the other two uncovered. Also, edge \(45\) requires at least one vertex from \(\{4,5\}\). These vertex sets are disjoint, so every cover has size at least \(2+1=3\). The set \(\{1,3,4\}\) covers all five edges: it meets \(12\) at \(1\), \(23\) at \(3\), \(13\) at both \(1\) and \(3\), \(34\) at \(3\) and \(4\), and \(45\) at \(4\). Hence \(\mathrm{OPT}=3\).
Check: The minimization ratio is \(\mathrm{ALG}/\mathrm{OPT}=4/3\). Substituting these values into the factor inequality gives \(4\le(4/3)\cdot3=4\). This is the ratio of this returned cover on this graph; it does not establish a factor-\(4/3\) guarantee for an algorithm on all graphs.
Worked Example: Maximum Cut on a Four-Vertex Graph
A cut is a partition of the vertex set into two parts; its size is the number of edges with endpoints in different parts. For a graph \(G=(V,E)\) with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\), consider the cut with parts \(S=\{1,2\}\) and \(V\setminus S=\{3,4\}\).
Check the four edges: \(12\) has both endpoints in \(S\), so it is not cut; \(23\) crosses the parts; \(31\) crosses; and \(34\) has both endpoints outside \(S\), so it is not cut. The returned cut has size \(\mathrm{ALG}=2\).
The triangle on \(\{1,2,3\}\) contributes at most two cut edges: if its vertices are split between two parts, two vertices are in the same part, and the edge between them is not cut. The edge \(34\) contributes at most one more. Therefore every cut has size at most \(2+1=3\). The cut with parts \(\{1,3\}\) and \(\{2,4\}\) cuts \(12,23,34\), while \(31\) is not cut, so a cut of size \(3\) exists and \(\mathrm{OPT}=3\).
Check: The maximization fraction is \(\mathrm{ALG}/\mathrm{OPT}=2/3\), so this cut achieves an \(\alpha=2/3\) fraction of optimum on this instance. Its reciprocal ratio is \(\mathrm{OPT}/\mathrm{ALG}=3/2\), which agrees with \(1/\alpha=1/(2/3)=3/2\).
Worked Example: Maximum Independent Set on a Path
An independent set is a set of vertices no two of which are adjacent. Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\), the path \(P_5\). Suppose an algorithm returns \(I=\{2,4\}\). Neither \(24\) nor any other edge has both endpoints in \(I\), since the listed edges are \(12,23,34,45\); therefore \(I\) is independent and \(\mathrm{ALG}=2\).
For an upper bound, each of the disjoint edges \(12\) and \(34\) allows at most one of its endpoints in an independent set. Vertex \(5\) contributes at most one further vertex. These sets of vertices, \(\{1,2\}\), \(\{3,4\}\), and \(\{5\}\), partition \(V\), so every independent set has size at most \(1+1+1=3\). The set \(\{1,3,5\}\) is independent: none of its vertex pairs is one of the listed edges. Thus \(\mathrm{OPT}=3\).
Check: The maximization fraction is \(\mathrm{ALG}/\mathrm{OPT}=2/3\). Direct substitution gives \(2\ge(2/3)\cdot3=2\). The independent set is feasible but not maximum, since the exhibited set of size \(3\) is larger.
Using Bounds to Certify a Ratio
Often it is difficult to calculate the exact optimum. A feasible solution gives one kind of information, while a bound on every feasible solution gives another. For minimization, a feasible solution of value \(U\) gives an upper bound on \(\mathrm{OPT}\), and a valid lower bound \(L\) can help limit the ratio. For maximization, a feasible solution of value \(L\) is a lower bound on \(\mathrm{OPT}\), and a valid upper bound \(U\) can help limit how far the solution might be from optimum.
Proof. In the minimization case, the returned feasible solution has value \(U\), so its ratio is \(U/\mathrm{OPT}\). Since \(L\le\mathrm{OPT}\) and \(L>0\), division by the positive quantities gives \(U/\mathrm{OPT}\le U/L\). In the maximization case, the returned feasible solution has value \(L\). Since \(\mathrm{OPT}\le U\) and \(U>0\), division gives \(L/\mathrm{OPT}\ge L/U\). These are the asserted bounds. \(\square\)
In the vertex-cover example, the edge arguments give the lower bound \(L=3\), and the displayed feasible cover gives \(U=4\). The upper bound on its ratio is therefore \(U/L=4/3\); the independently verified cover of size \(3\) shows that the actual optimum is \(3\). In the maximum-cut example, a cut of size \(2\) gives a feasible lower bound, and the triangle-plus-edge argument gives upper bound \(3\). The fraction certified from those bounds is \(2/3\), which is exact here because a cut of size \(3\) was exhibited.
To prove an algorithm-wide guarantee, the corresponding inequality must hold for every allowed input. For example, a factor-\(\rho\) guarantee for vertex cover requires that every returned cover \(C\) satisfy \(|C|\le\rho\,\mathrm{OPT}\) on every graph in the stated domain. Calculating an exact optimum on one graph establishes only that graph’s ratio. The next topics in this unit study particular approximation algorithms and their proofs; a ratio calculation alone does not provide such an algorithm or proof.
Common Pitfall: Reversing the Maximization Ratio
For a maximization problem, the candidate value is at most the optimum. In the maximum-cut example, writing \(\mathrm{ALG}/\mathrm{OPT}=3/2\) would be a wrong calculation: substituting the actual values gives \(2/3\), not \(3/2\). The number \(3/2\) is the reciprocal \(\mathrm{OPT}/\mathrm{ALG}\). It is a valid reciprocal ratio, but it corresponds to an approximation factor of \(2/3\), not \(3/2\). State which convention is being used before interpreting a numerical ratio.
A second caution concerns zero values. If a graph has no edges, its maximum-cut optimum is \(0\), so \(\mathrm{ALG}/\mathrm{OPT}\) is undefined. The inequality form \(\mathrm{ALG}\ge\alpha\,\mathrm{OPT}\) still makes sense and is satisfied by a feasible cut of value \(0\). If the input domain includes such graphs, specify the guarantee by inequalities or treat zero-optimum instances separately rather than silently dividing by zero.
Check Your Understanding
For each question, distinguish what follows from a single instance from what would require a guarantee over all inputs.
- A minimization algorithm returns a solution of value \(15\), while the optimum is \(12\). What is its instance ratio, and what factor inequality does that ratio express?
- A maximization algorithm returns value \(8\) when the optimum is \(10\). Give both the achieved fraction of optimum and the reciprocal ratio.
- Why does exhibiting a vertex cover of size \(4\) prove an upper bound on the minimum vertex-cover size, rather than a lower bound?
- For the graph in the maximum-cut example, verify the size of the cut with parts \(\{1,3\}\) and \(\{2,4\}\), listing which edges cross.
- What issue arises if one defines a ratio by dividing by the optimum on an input whose optimum is zero? Give an inequality form that avoids this division for a maximization guarantee.