Approximation ratios and inapproximability

For a minimization problem with nonnegative costs, a factor alpha algorithm returns a feasible solution of cost at most alpha times optimum, where alpha is at least one. Feasibility also implies its cost is at least optimum. For maximization, a common convention requires value at least optimum divided by alpha. State the convention because some literature instead reports a fraction at most one. If optimum is zero, the multiplicative inequality still has meaning and forces a zero-cost answer in the minimization setting; dividing by zero to quote a numerical ratio does not.

A ratio is a worst-case guarantee over the specified instance family, with a separate polynomial-time requirement in the encoded input length. It need not describe typical performance. An additive error bound, an expected ratio for a randomized algorithm, and a high-probability guarantee are distinct statements. Comparing a returned cost with the best answer found by another heuristic does not certify its ratio to the true optimum. An independent bound on what any feasible solution can achieve supplies the missing reference point.

For unweighted vertex cover on a finite undirected simple graph, greedily build a maximal matching M: choose an edge, keep it, and remove all edges incident to its endpoints before continuing. Return both endpoints of every chosen edge. The returned set covers every edge, because an uncovered edge would be disjoint from all chosen endpoints and could have extended the matching, contradicting maximality. Maximal need not mean maximum-size; no largest-matching computation is required.

Every vertex cover must include at least one endpoint of every matching edge. Matching edges are vertex-disjoint, so these obligations require distinct selected vertices, yielding optimum at least |M|. The returned cover has exactly 2|M| vertices, so its size is at most twice optimum. This proof combines a feasible construction with a lower-bound certificate. It applies to unit vertex costs. Selecting both endpoints under arbitrary weights can be arbitrarily poor, because the matching argument counts vertices rather than their costs.

NP-hardness of exact optimization does not automatically rule out good approximations. To prove a particular approximation threshold impossible under a complexity assumption, one commonly constructs a gap reduction: yes source instances have optimum in one range, while no source instances have optimum in a separated range. An approximation stronger than that gap would distinguish the two. The reduction must preserve the allowed family, objective orientation, polynomial encoding size, and any promises; a yes/no reduction without a quantitative gap is insufficient.

A simple barrier illustrates the role of assumptions without claiming a sharp vertex-cover threshold. For integer-valued graph objectives bounded by n, a fully polynomial approximation scheme with sufficiently tiny error can reveal the exact integer optimum. Handle the empty graph directly. For a vertex-cover instance with n at least one, choosing epsilon = 1/(2n) in a hypothetical FPTAS gives cost at most optimum plus optimum/(2n), hence at most optimum plus one half because optimum is at most n. The returned cost is an integer strictly below optimum plus one, forcing exact optimality. Its time would remain polynomial because an FPTAS is polynomial in both input length and 1/epsilon. Thus such an FPTAS for general vertex cover would imply P = NP. A PTAS allows arbitrary dependence on 1/epsilon and does not support that same runtime conclusion.