Approximation Algorithms for Problems You Cannot Solve Exactly

Many optimization problems are easy to state and expensive to solve exactly: choose monitoring bundles that cover every subsystem, place facilities at low cost, or find the best cut among exponentially many choices. Exact algorithms remain valuable for small or structured instances, but may be too slow for online decisions or large planning runs.

An approximation algorithm makes a precise compromise: it runs within a stated resource bound, always returns a feasible solution, and proves how far that solution can be from optimal. That last property separates approximation from optimism. A heuristic may work extremely well on familiar data, but without a guarantee it offers no bound on an unseen instance.

The central thesis is that a useful approximate answer needs both an incumbent solution and a mathematical reference point. That reference may be a charging proof, a relaxation no exact solution can beat, or a local-optimality argument. This article develops those tools around weighted set cover, rounding, and local search.

Define the Approximation Contract #

Let $OPT(I)$ be the optimal objective for instance $I$, and let $ALG(I)$ be the objective returned by an algorithm. For a minimization problem with positive objectives, an $\alpha$-approximation satisfies

for every valid instance, where $\alpha \ge 1$. For a maximization problem, a common convention is

Another common maximization statement is $ALG(I)\ge(1-\epsilon)OPT(I)$. The convention must be written down; saying “a 0.9 approximation” is ambiguous without it.

The ratio normally assumes that the algorithm returns a feasible solution. A schedule with lower cost because it omits required jobs is not an approximation; it solves a relaxed problem. Feasibility, objective computation, and the ratio proof are separate obligations.

Multiplicative ratios can become meaningless when objectives are zero or negative. An additive guarantee such as $ALG\le OPT+k$, or a problem-specific normalization, may be more appropriate. Guarantees may also depend on assumptions: nonnegative weights, a metric distance satisfying the triangle inequality, bounded item sizes, or a particular graph class. An implementation that accepts broader inputs must either validate those assumptions or clearly drop the guarantee.

Guarantees may be constant-factor, input-dependent such as $1+\ln n$, or parameterized by an accuracy target. A PTAS obtains a $(1+\epsilon)$ ratio in polynomial time for fixed $\epsilon$, while an FPTAS is polynomial in both input size and $1/\epsilon$. These labels describe proofs, not typical quality: a 2-approximation may often be optimal, while an unproven heuristic may win benchmarks yet fail without limit on another family.

Work Through Greedy Weighted Set Cover #

Weighted set cover begins with a universe $U$ of required elements. Each available set $S$ covers some elements and has positive cost $c(S)$. The goal is to cover every element at minimum total cost. The greedy algorithm repeatedly chooses the set with the lowest cost per newly covered element:

where $R$ is the set of requirements still uncovered. Sets with $|S\cap R|=0$ are ignored.

Consider six subsystems: API, worker, database, cache, queue, and search. Four monitoring bundles are available:

Greedy first chooses Core because 0.75 is the smallest score. Only queue and search remain. Async covers both for cost 2.0, so greedy returns {Core, Async} with total cost 5.0.

That answer is feasible but not optimal. {Ingress, Data} covers all six subsystems for 4.8. The approximation ratio on this instance is

The example exposes an important limitation: greedy scores the immediate uncovered elements but does not account for how a choice changes the shape of the remainder. Core looks slightly more efficient at first, yet it leaves exactly the pair served by an otherwise expensive bundle. The guarantee does not claim greedy is optimal; it limits how bad this myopia can become.

A production implementation should define deterministic tie-breaking, reject invalid costs, and report uncoverable elements. It may remove empty or dominated sets, but only when permissions, capacities, and other omitted constraints do not distinguish them.

Derive the Harmonic Guarantee by Charging #

Greedy weighted set cover is an $H_n$-approximation, where $n=|U|$ and

The proof assigns a price to each element when it is first covered. If greedy picks a set of cost $c$ that newly covers $k$ elements, charge each of those elements $c/k$. The total charge equals the total cost because every selected set’s cost is distributed exactly once.

Suppose $r$ elements remain before a greedy step. The sets in an optimal solution collectively cover those $r$ elements and have total cost $OPT$. Even if their coverages overlap, at least one optimal set must have cost per newly covered remaining element at most $OPT/r$; otherwise their combined cost would exceed $OPT$ before accounting for all $r$ elements. Greedy chooses a set with no worse score, so each element covered at this step receives charge at most $OPT/r$.

Order elements by when greedy covers them. The first can be charged at most $OPT/n$, the next at most $OPT/(n-1)$, and the last at most $OPT$. Summing gives

The proof is also a design pattern: map algorithm cost onto atomic obligations, then bound each obligation using a comparison solution.

The theorem bounds valid instances under its assumptions; it does not predict the observed ratio. Changing the score also changes the claim. Maximum raw coverage ignores cost, and domain priority multipliers invalidate the original proof unless analyzed separately.

Use Relaxations to Obtain Lower Bounds #

A relaxation removes a hard constraint so the resulting problem is easier and at least as optimistic as the original. For minimization, its optimum is a lower bound on $OPT$; no feasible integral solution can cost less. The gap between a feasible incumbent and that lower bound quantifies how much room for improvement remains even when the exact optimum is unknown.

The linear programming relaxation of set cover assigns a fractional variable $x_S\ge0$ to each set:

The integral problem additionally requires each $x_S$ to be 0 or 1. Removing integrality can produce an unrealistically cheap fractional cover, but that is precisely why the LP optimum is a useful lower bound. Turning it back into an integral solution requires rounding, and the rounding loss determines the approximation ratio.

Weighted vertex cover gives a clean rounding example. Choose vertices so every edge has at least one selected endpoint. Its LP has variables $x_v\ge0$ and constraints $x_u+x_v\ge1$ for every edge $(u,v)$. Select every vertex with $x_v\ge1/2$. Every edge remains covered because at least one endpoint must meet that threshold. The rounded cost is at most twice the fractional objective:

Thus rounding yields a 2-approximation. The first inequality is pointwise: a selected vertex’s full weight is no more than twice its fractional contribution. The second uses the relaxation as a lower bound.

The value of a relaxation depends on its integrality gap, the worst ratio between integral and relaxed optima. A weak lower bound certifies only a weak approximation. Numerical rounding also requires a deliberate tolerance followed by an independent feasibility check.

Improve and Prove with Local Search #

Local search starts from a feasible solution and repeatedly applies an improving move from a defined neighborhood. Examples include swapping one selected facility, moving one job, replacing a few sets, or flipping one vertex across a cut. It stops at a local optimum when no permitted move improves the objective.

Local optimality alone is not a guarantee. A solution can be excellent against one-item moves and terrible compared with a coordinated ten-item change. A proof must connect the chosen neighborhood to a global bound. Enlarging the neighborhood can improve solution quality but makes each iteration more expensive.

Max-Cut provides a compact example. Partition the vertices of an undirected graph to maximize the weight of edges crossing the partition. Start with any partition. While a vertex has more incident weight staying on its own side than crossing, move it to the other side. Every move strictly increases cut weight, so with finite discrete weights the process terminates.

At a one-flip local optimum, each vertex has at least as much incident weight crossing as remaining on its side; otherwise flipping it would help. Summing this inequality over vertices counts every edge twice. Therefore crossing weight is at least noncrossing weight, so the cut contains at least half of all edge weight. Since no cut can exceed total edge weight, the result is at least $OPT/2$, conventionally a 2-approximation for maximization.

Floating-point noise can cause cycling, so use exact weights where possible or a documented improvement tolerance and deterministic tie rule. Incremental delta costs should be checked against periodic full recomputation. A time-budget stop preserves the incumbent but not a proof that requires local optimality.

Know When a Heuristic Has No Guarantee #

Greedy selection, local search, simulated annealing, evolutionary search, and learned policies are families of techniques, not guarantees by themselves. The weighted set cover rule has a harmonic proof; a slightly different greedy score may not. One-flip Max-Cut has a factor bound; one-flip local search for another objective may have an arbitrarily poor local optimum.

Heuristics remain useful when models contain side constraints that defeat clean analysis, when instances have stable structure not captured by worst-case theory, or when they refine an already feasible guaranteed solution. The honest interface distinguishes three claims:

• Feasibility claim: an independent checker confirms all hard constraints.
• Bound claim: a theorem applies because its assumptions and stopping conditions hold.
• Empirical claim: evaluation on a declared instance suite showed a distribution of objective values and runtimes.

Random testing cannot establish a bound, and a weak worst-case ratio does not imply weak typical performance. Report proof and empirical quality as separate evidence.

Hybrid designs often work well. Run a proven approximation to get a fast feasible incumbent, improve it with bounded local search, and compare it with a relaxation lower bound. The extra heuristic can only improve a minimization incumbent if it accepts strictly cheaper feasible moves, while the original approximation bound remains valid. If later steps can replace the solution with an unchecked learned proposal, the guarantee is lost.

Verify Feasibility, Bounds, and Operations #

Build a tiny exact oracle before optimizing. Enumerate all subsets for small set-cover instances, or solve a small integer program, then compare greedy and rounded outputs with the true optimum. Include empty universes, an uncoverable element, duplicate and dominated sets, equal scores, zero-size sets, extreme costs, and instances deliberately shaped to make greedy nonoptimal.

Property tests should verify coverage and recompute cost from selected identifiers. Permuting sets must not change objective quality, and scaling all positive costs equally should preserve ratio-based choices. For local search, enumerate every allowed move at termination and assert none improves the result.

When exact $OPT$ is unavailable, retain certified bounds. For minimization, let $L$ be a valid positive lower bound from a relaxation and $U$ the cost of a feasible incumbent. Then

The gap $U/L$ may certify a much stronger result for one instance than the worst-case theorem. Never label a heuristic objective as a lower bound merely because it is smaller; the bound must come from a valid relaxation, dual solution, or other proof.

Operational telemetry should record instance size, algorithm parameters, runtime, iterations, feasibility, incumbent, certified lower bound, and stop reason. Alert first on infeasibility or invalid assumptions, and preserve deterministic replay inputs including tie-breaking and tolerances.

Approximation is appropriate when exact optimization misses the time or scale budget and a bounded compromise is acceptable. Choose the guarantee to match the consequence: a harmonic set cover may suit planning, while a regulated allocation may require exact review. Keep the objective faithful to the real cost, validate every assumption, and make feasibility independently checkable.

The durable pattern is to produce a feasible incumbent, compare it with something the optimum cannot beat, and prove how the algorithm transforms one into the other. Greedy charging, relaxation and rounding, and local-optimality arguments are different tools for that same job. They turn “this answer seems good” into a statement that remains meaningful on inputs no benchmark happened to contain.