---
title: "Approximation and primal-dual design"
---

## Prime

Some problems are NP-hard: no known algorithm solves them fast in the worst case, and probably none
exists. The traveling salesman, set cover, and many scheduling problems live here. Giving up is not an
option, because businesses route trucks and place servers every day. The move is not to solve the
impossible problem exactly, but to change the promise: return an answer provably within a factor of the
best.

## Probe

::: {.callout-note title="Try first (no AI)"}
You must cover a set of neighborhoods with the fewest cell towers, where each candidate tower covers some
subset of neighborhoods. Choosing the truly minimum number of towers is NP-hard. Design a fast, sensible
rule anyway. How good can you promise it is, compared to the unknown best?
:::

The natural rule is greedy: keep adding the tower that covers the most still-uncovered neighborhoods. It
is fast and obvious. The real question, the one that this module answers, is how far from optimal greedy can be,
and whether you can *prove* a bound.

## Point

> **Primitive: submodularity, or diminishing returns.** Coverage has a property: adding a set helps less once
> other sets are already chosen. When the objective is submodular and monotone, greedy is not just
> reasonable, it is provably within a factor `H(n)`, about `ln n`, of optimal.

The set-cover reference in `implementations/approx.py` is exactly this greedy rule, and its property test
confirms both that it covers everything and that its size stays within the `ln n` factor of the brute-force
optimum on small instances.

Now the traveling salesman, under the mild assumption that distances obey the triangle inequality (a
detour is never shorter). Here a different composition gives a clean guarantee.

> **Primitive: build a lower-bound structure, then round it up.** A minimum spanning tree is a lower bound on any
> tour (delete one edge of the optimal tour and you get a spanning tree). Walk the tree in preorder,
> shortcutting past already-visited cities. The triangle inequality guarantees that the shortcut tour is no
> longer than twice the tree, hence at most twice the optimal tour.

```python
preorder(0)                       # walk the MST, listing cities in first-visit order
length = sum(dist[order[i]][order[(i + 1) % n]] for i in range(n))
```

The property test checks that this double-MST tour visits every city once and always lands between the
optimum and twice the optimum.

## Attach

This is the module where primitives from everywhere compose into guarantees.

> **Christofides = contraction + MST-greedy + matching + the triangle-inequality certificate.** Replace the
> "double every edge" step with a smarter fix: add a minimum-weight perfect matching on just the
> odd-degree vertices (the smart eulerization, taught in this chapter beside the double tree; the
> matching is used through its contract). Hierholzer's walk turns the even-degree multigraph into an
> Euler tour, and skipping repeated vertices shortcuts it into a tour of the cities. That drops the
> ratio from 2 to 1.5. Same bricks, better composition, better promise.

- **Relaxation and rounding** (from module M8): solve the LP relaxation of an integer problem, then round.
  The LP optimum is a lower bound that certifies the rounding's quality.
- **Multiplicative weights** is a meta-algorithm that approximately solves LPs and zero-sum games by
  reweighting experts, and it reappears in online learning.

The transferable move: when exact is impossible, find a structure that lower-bounds the optimum, build your
answer from it, and let a certificate (a matroid, submodularity, the triangle inequality, an LP bound) turn
"seems good" into "provably within a factor."

## Strengthen

- Run greedy set cover and confirm it stays within the `ln n` factor of the brute-force optimum, as the
  property test does. Construct the classic instance where greedy is exactly a `ln n` factor off.
- Build a double-MST tour on random cities and measure its ratio to the optimal tour.
- Trace how Christofides improves the ratio to 1.5 by matching the odd-degree vertices instead of doubling the tree's edges.
- Adversarial input: a set-cover instance designed to make greedy pick many small sets. Why does the bound
  still hold?

## Test

::: {.callout-note title="No-AI check"}
You must place monitoring sensors to cover all road segments, using as few sensors as possible, and the exact
problem is NP-hard. Which greedy rule do you use, which primitive proves it is within `ln n` of optimal, and what
property must the coverage function have for that proof to apply? Separately, for a delivery tour on a map,
what guarantee can you promise cheaply, and which assumption about distances does it need?
:::

## Frontier map

- **Online algorithms.** Decisions made before the whole input is known, measured by competitive ratio
  against a hindsight optimum. Signature: irrevocable choices under uncertainty. Reach for it in caching and
  scheduling.
- **Bandits and no-regret learning.** Repeatedly choose actions and learn from feedback, driving average
  regret to zero. Signature: explore versus exploit. Multiplicative weights is the bridge.
