Skip to content

How good can a fast answer be? Approximation limits (Unique Games)

Some planning questions — split a graph into two sides cutting as many links as possible, pick the fewest people who touch every conflict, open \(k\) warehouses as close as possible to every store — have no known fast exact algorithm. Teams then use a fast approximate one and, sooner or later, someone asks for a better worst-case promise: "can we always be within 10% of optimal?" This page explains what the mathematics says about how good such promises can get, what the library's router returns when asked, and what it does not guarantee.

It covers two entries of the companion math catalog: Unique Games and optimal approximation thresholds (catalog result 102), and the metric \(k\)-median threshold \(1+2/e\) (catalog result 125). It assumes you know what a graph is. Symbols are collected in How to read these pages; terms are in the glossary.

The question, in product terms

A ride-hailing marketplace builds a feasibility graph every few seconds: drivers on one side, riders on the other, a line between a driver and a rider when the pickup time is short enough. Around the actual matching it runs three graph computations, each with a temptation:

  • Max-Cut: split the participants into two groups so that as many lines as possible run between the groups. The temptation is to fund a search for an algorithm with a better worst-case ratio.
  • Vertex cover: the smallest set of participants that touches every line (whom to ping so no pairing is offered on stale data). Same temptation.
  • \(k\)-median (in the facility_location case): open \(k\) warehouses out of a candidate list so the total store-to-warehouse distance is small. Same temptation: "promise 1.5× of optimal".

An approximation ratio is the promise: "on every input, our answer is within this factor of the best possible answer". For Max-Cut a ratio of 0.88 means "we always cut at least 88% as many lines as the best split"; for vertex cover and \(k\)-median a ratio of 2 means "we never use more than twice the optimum".

The library's router (dispatch) answers these requests with two things: the result of a simple, fast procedure, and a frozen factor — the catalog's best possible worst-case ratio — which it refuses to improve on. "Frozen" means: this is the number not to promise past. It is not a promise that this code achieves it.

Intuition: why some ratios stop improving

For many hard problems, decades of work produced an algorithm with some ratio and then stopped. The Unique Games Conjecture (UGC, Khot 2002) explains why many of those stopping points may be final.

A unique game is a puzzle: give every node of a graph a label from a small set, where each line says "if this end has label \(a\), the other end must have label \(\pi(a)\)" for some fixed one-to-one map \(\pi\). If every constraint can be satisfied, a simple propagation finds the labels. The conjecture says that telling "almost every constraint can be satisfied" apart from "almost none can" is NP-hard. If that is true, then, by reductions, beating the Goemans–Williamson ratio for Max-Cut or the factor 2 for vertex cover is also NP-hard — so the ratios we already have would be the best possible for fast algorithms.

The marketplace graph shows the gap between a worst-case number and one instance. It has three drivers (0, 1, 2), three riders (3, 4, 5) and six feasible pairings, forming one cycle:

graph LR
    d0((driver 0)) --- r3((rider 3))
    r3 --- d1((driver 1))
    d1 --- r5((rider 5))
    r5 --- d2((driver 2))
    d2 --- r4((rider 4))
    r4 --- d0

Putting all drivers on one side and all riders on the other cuts all six lines, so the best cut is 6. The three drivers alone touch every line, so the smallest vertex cover is 3.

Worked example

Run the case:

uv run grounded-decision examples matching_marketplace

It prints (abridged):

tick 0  Max-Cut on the feasibility graph
  OUTPUT ok=True
         spectral cut with local search 6/6 edges (at least m/2 guaranteed); α_GW=0.8786 is the best ratio any polynomial algorithm can promise if the Unique Games Conjecture holds, not a guarantee of this one
tick 1  vertex cover on the same graph
         the 3 drivers alone cover every pairing, so the optimum is at most 3; this cover has 6 participants
  OUTPUT ok=True
         maximal-matching cover size 6 (at most 2x optimal); factor 2 is optimal for general graphs only if the Unique Games Conjecture holds, and bipartite graphs can be solved exactly

So on this graph the Max-Cut procedure finds the best cut (6 of 6), and the vertex-cover procedure returns all 6 participants — exactly twice the optimum of 3, the worst its factor 2 allows.

The same calls from Python, with the full result:

from grounded_decision import Envelope, Subgoal, dispatch

adj = {0: {3, 4}, 1: {3, 5}, 2: {4, 5}, 3: {0, 1}, 4: {0, 2}, 5: {1, 2}}
dispatch(Subgoal("max_cut", Envelope.UGC_OPT, {"adj": adj})).to_dict()

{
  "subgoal": "max_cut",
  "envelope": "ugc_opt",
  "ok": true,
  "detail": "spectral cut with local search 6/6 edges (at least m/2 guaranteed); α_GW=0.8786 is the best ratio any polynomial algorithm can promise if the Unique Games Conjecture holds, not a guarantee of this one",
  "value": {
    "name": "max_cut",
    "value": 6.0,
    "factor_claimed": 0.8785672058,
    "catalog_optimal": true,
    "detail": "spectral cut with local search 6/6 edges (at least m/2 guaranteed); α_GW=0.8786 is the best ratio any polynomial algorithm can promise if the Unique Games Conjecture holds, not a guarantee of this one"
  }
}

For \(k\)-median the router does not solve anything; it returns the frozen number:

uv run grounded-decision examples facility_location

tick 0  k-median worst-case guarantee
  OUTPUT ok=True
         do not claim worst-case factor below 1.7358 (catalog 125)
tick 1  measure the plan on this instance
         greedy / optimal = 1.229 on this instance

The second tick is the useful habit: a greedy plan was measured against the exact optimum (possible only because the instance has 5 candidate sites and 7 stores) and came out 1.229 times worse on this instance. That is an instance fact, not a worst-case promise.

The precise statements

Max-Cut. Given a graph with \(m\) edges, choose a split of the vertices into two sides; the value is the number of edges with one end on each side. Goemans and Williamson (1995) solve a semidefinite program and round it with a random hyperplane; the expected cut is at least \(\alpha_{\mathrm{GW}} \approx 0.8786\) times the optimum (gw_alpha() returns 0.8785672058).

Vertex cover. Choose the fewest vertices such that every edge has at least one chosen end. Taking both ends of every edge of a maximal matching gives a cover at most twice the optimum, because any cover must contain at least one end of each matching edge, and those edges share no ends.

Metric \(k\)-median with candidate facilities. Given clients, candidate facility sites, distances obeying the triangle inequality, and \(k\), open at most \(k\) sites and assign each client to its nearest open site; the cost is the sum of distances. The constant \(1 + 2/e \approx 1.7357588823428847\) is a lower bound on hardness: no polynomial-time algorithm can guarantee a better factor unless a standard complexity assumption fails.

Where this result stands

In the wider literature:

  • The Unique Games Conjecture is open. Its weaker 2-to-2 variant was proved in 2018 (Khot, Minzer and Safra, with Dinur and Kindler).
  • Max-Cut: beating \(\alpha_{\mathrm{GW}}\) is NP-hard assuming the Unique Games Conjecture (Khot, Kindler, Mossel and O'Donnell). Without that assumption, beating \(16/17 \approx 0.941\) is NP-hard (Håstad).
  • Vertex cover: beating 2 is NP-hard assuming the Unique Games Conjecture (Khot and Regev). Without it, beating \(\sqrt 2 \approx 1.414\) is NP-hard (Khot, Minzer and Safra).
  • Metric \(k\)-median: no polynomial algorithm can beat \(1+2/e\) under a standard complexity assumption (Jain, Mahdian and Saberi). No known polynomial algorithm achieves it: to our knowledge the best published polynomial-time ratios are roughly 2 to 2.7, depending on the paper, and \(1+2/e+\varepsilon\) is known only in time exponential in \(k\) (Cohen-Addad and coauthors, 2019).

In this project's math catalog:

  • Result 102 claims a proof of the Unique Games Conjecture itself, plus direct NP-hardness reductions for Max-Cut beyond \(\alpha_{\mathrm{GW}}\), vertex cover below 2, Min-UnCut and directed feedback vertex set. These are checked by Lean statements of the gap reductions in the companion math catalog.
  • Result 125 claims a deterministic polynomial-time \((1+2/e+\varepsilon)\)-approximation for every fixed \(\varepsilon > 0\), so that \(1+2/e\) would be the exact threshold assuming P ≠ NP. The library pins it as a manuscript result (lean=False). A Lean statement in the catalog covers a related recovery algorithm, not the full threshold.

What this library relies on: only the frozen numbers, as a ceiling on what may be claimed. No decision depends on whether the conjecture is true. See Where each result stands.

The trust levels (see How to read these pages): REF_UGC (102) is lean, meaning a machine-checked statement exists in the catalog; the library does not run or re-check it. REF_K_MEDIAN (125) is paper: a written result the router treats as policy.

What the code does, and how it differs from the theorems

All three handlers live in grounded_decision.router.ugc and are reached through dispatch. A graph is dict[int, set[int]] listing both directions of every edge.

Subgoal What runs What it guarantees Factor it reports
max_cut Split by the sign of the top eigenvector of the graph Laplacian, then move single vertices while that grows the cut At least \(m/2\) edges cut \(\alpha_{\mathrm{GW}}\), as the frozen target
vertex_cover Both ends of a greedy maximal matching (vertex order = dict insertion order) At most twice the minimum cover 2
k_median Nothing; the payload is ignored Nothing is placed \(1+2/e\), as the claim floor

The differences that matter:

  • The Max-Cut procedure is not Goemans–Williamson. No semidefinite program, no random hyperplane. The local search ends with every vertex having at least half its edges cut, which is where the \(m/2\) guarantee comes from — a much weaker promise than 0.8786. The field factor_claimed holds \(\alpha_{\mathrm{GW}}\) as a reference number, and catalog_optimal: true describes the factor, not the procedure. Read detail.
  • It can fall below the Goemans–Williamson factor on a real graph (\(\alpha_{\mathrm{GW}}\)). On 300 random graphs with 4–10 vertices (edge probability 0.4, seed 1), compared against brute force, the procedure was below the optimum on 22 and its worst ratio was 0.857:
import itertools, random
from grounded_decision.router.ugc import max_cut_spectral


def best_cut(adj):
    vs = sorted(adj)
    edges = [(u, v) for u in adj for v in adj[u] if u < v]
    best = 0
    for mask in range(1 << (len(vs) - 1)):
        side = {vs[i] for i in range(len(vs)) if mask >> i & 1}
        best = max(best, sum((u in side) != (v in side) for u, v in edges))
    return best, len(edges)


random.seed(1)
below, worst = 0, 1.0
for _ in range(300):
    n = random.randint(4, 10)
    adj = {i: set() for i in range(n)}
    for a, b in itertools.combinations(range(n), 2):
        if random.random() < 0.4:
            adj[a].add(b)
            adj[b].add(a)
    optimum, m = best_cut(adj)
    if m == 0:
        continue
    value = max_cut_spectral(adj).value
    below += value < optimum
    worst = min(worst, value / optimum)
print(below, round(worst, 3))  # 22 0.857
  • Vertex cover ignores easy structure. On bipartite graphs (like the marketplace graph) a minimum vertex cover can be found exactly in polynomial time from a maximum matching (König's theorem). The router does not check for this and returns the general 2-approximation — 6 participants where 3 suffice.
  • \(k\)-median is a note, not a solver. It returns value = factor_claimed = 1.7357588823428847 and opens no facilities.
  • Envelopes. Each request carries an Envelope tag (p_exact, fpras, ugc_opt, undec, exptime_trap) saying which hardness class the caller believes it is in. Any subgoal tagged UNDEC, EXPTIME_TRAP or FPRAS (no FPRAS handler exists) is refused before a handler runs; max_cut accepts UGC_OPT or P_EXACT. Successful results are tagged ugc_opt. See Refusals.
  • No size cap. Limits does not bound these subgoals. Max-Cut does a dense \(n \times n\) eigendecomposition, about \(n^3\) work.

The full result shape and all handlers are in the router API and router internals.

Limits, and when this matters in practice

What a result here does not establish:

  • That your answer is within \(\alpha_{\mathrm{GW}}\) (or any factor better than \(1/2\)) of the best cut. Only \(m/2\) is guaranteed.
  • That any algorithm, here or elsewhere, achieves \(1+2/e\) for \(k\)-median in polynomial time. The number is a floor on what may be claimed, never a ratio to publish for your planner.
  • That the hardness numbers are unconditional. In the wider literature the Max-Cut and vertex-cover thresholds hold assuming the Unique Games Conjecture.

What to do instead of hunting a better worst-case ratio:

  • Measure per instance. Compare your plan with a lower bound (an LP relaxation for \(k\)-median, a matching size for vertex cover) and track the gap, as the facility_location case does.
  • Solve small or structured instances exactly. An integer-program solver handles hundreds of variables; bipartite vertex cover is exact via König's theorem.
  • Quote what the code guarantees. For max_cut, that is \(m/2\); for vertex_cover, that is 2.

There is no Limits setting for these subgoals; other parameters are covered in Choosing parameters.