A Poor Approximation Ratio Predicts Little About How a Heuristic Behaves — Epoche B2
Re-evaluating Heuristics: Beyond Worst-Case Bounds in NP-Hard Problems The study of computational complexity reveals a fundamental divide between problems solvable efficiently (in polynomial time) and those that are seemingly intractable. For problems classified as NP-hard, finding an optimal solution in polynomial time is widely believed to be impossible. Despite this theoretical barrier, many NP-hard problems arise in critical real-world applications, from logistics and scheduling to resource allocation and circuit design. This necessitates the use of heuristics and approximation algorithms [1] , which aim to find solutions that are "good enough" within a practical time frame. A common method for evaluating these algorithms is through worst-case performance guarantees, often expressed as an approximation ratio [2] . This essay explores why, for many NP-hard problems, the poor worst-case performance guarantees of simple heuristics do not always reflect their considerable practical utility, advocating for a more balanced perspective that incorporates average-case analysis and empirical evidence. The Landscape of Intractability: NP-Hard Problems and Approximation A problem is in class P if a deterministic algorithm solves it in polynomial time, its runtime bounded by $O(n^c)$ for some constant $c$ with $n$ the input size. The class NP contains problems for which a proposed solution can be verified in polynomial time. NP-hard problems are at least as hard as every problem in NP: a polynomial-time algorithm for one would give a polynomial-time algorithm for all of NP. Classic examples include the Travelling Salesperson Problem (TSP), Set Cover, and satisfiability problems, and for these we resort to approximation algorithms. An approximation algorithm for an NP-hard problem is a polynomial-time algorithm that returns a solution whose value is guaranteed to be within a certain factor of the optimal solution. This guarantee is quantified by the approximation ratio . For a minimisation problem, such as Set Cover or TSP, where we seek the smallest possible cost, the approximation ratio $\rho(I)$ for an input instance $I$ is defined as: $$ \rho(I) = \frac{A(I)}{OPT(I)} $$ where $A(I)$ is the cost of the solution found by the approximation algorithm, and $OPT(I)$ is the cost of the optimal solution for input $I$. For a valid approximation algorithm, we require $\rho(I) \ge 1$, with values closer to $1$ indicating better performance. Conversely, for a maximisation problem, such as MAX-3SAT, where we seek the largest possible value, the approximation ratio $\alpha(I)$ is defined as: $$ \alpha(I) = \frac{A(I)}{OPT(I)} $$ Here, we require $\alpha(I) \le 1$, with values closer to $1$ indicating better performance. An algorithm is said to have an approximation ratio of $\rho$ (or $\alpha$) if $\rho(I) \le \rho$ (or $\alpha(I) \ge \alpha$) for all possible input instances $I$. This worst-case guarantee is a powerful theoretical statement, ensuring a minimum level of solution quality regardless of the input. The Rigour of Worst-Case Analysis: Strengths and Limitations Worst-case analysis is a cornerstone of theoretical computer science. It provides a formal, rigorous guarantee on an algorithm's performance, ensuring that its output will never be worse than a specified bound, irrespective of the specific input instance. This robustness is invaluable in safety-critical systems or scenarios where failure to meet a minimum quality threshold could have severe consequences. For instance, knowing that an algorithm for a network routing problem will always find a path no more than twice the optimal length provides a strong assurance. However, this strength can also be a limitation. To derive a worst-case bound, the analysis typically constructs a highly specific "pathological" instance engineered to exploit the algorithm's weakness and push its performance to the extreme — and such instances may be exceedingly rare, or absent altogether, in real applications. Consequently, an algorithm's worst-case guarantee — for a minimisation problem, the upper bound $\rho$ on the achieved ratio $\rho(I)$, equivalently a floor on solution quality — may be attained only on instances that are vanishingly rare, and so may be a poor predictor of typical utility. A heuristic with a theoretically poor worst-case bound might, in practice, consistently deliver high-quality solutions for the types of inputs it commonly encounters. This discrepancy highlights the gap between theoretical guarantees and practical effectiveness, leading to a common misconception that algorithms with poor worst-case bounds are inherently ineffective. Illustrative Heuristics and Their Guarantees To illustrate this point, let us examine several well-known NP-hard problems and their approximation algorithms. Set Cover Problem The Set Cover problem is a classical NP-hard minimisation problem. Given a universe $U$ of $n$ elements and a collection of $m$ sets $S = \{S_1, S_2, \dots, S_m\}$, where each $S_j \subseteq U$, the goal is to find the smallest subcollection of sets whose union is $U$. A simple and widely used approach is the greedy algorithm : at each step, select the set that covers the maximum number of currently uncovered elements. Repeat until all elements are covered. While intuitive, the greedy algorithm does not always yield an optimal solution. Chvátal's analysis bounds its worst-case approximation ratio by the $s$-th harmonic number $H(s)$, where $s = \max_j |S_j|$ is the size of the largest set in the collection. The parameter is a set size, not an element frequency, and the proof shows why: each newly covered element is charged a price equal to one over the number of elements covered at that step, and the prices charged inside a single set of the optimal cover, which has at most $s$ elements, sum to at most $1 + \tfrac{1}{2} + \dots + \tfrac{1}{s}$. The harmonic number is $$ H(s) = \sum_{i=1}^{s} \frac{1}{i} $$ and for large $s$ it grows loga