vault

Bitmask DP

21 min read

Bitmask DP

Bitmask DP is the family of dynamic-programming algorithms whose state space is the powerset of a small ground set — that is, states correspond one-to-one with subsets S ⊆ {0, 1, ..., n-1}, encoded as n-bit integers 0 ≤ mask < 2^n. Treating subsets as integers turns set-membership tests into bit operations ((mask >> i) & 1) and set construction into bit twiddling (mask | (1 << i)), exposing an extremely cache-friendly, branch-free implementation that is dramatically faster than any pointer-based set representation. Bitmask DP is the standard tool when the optimal substructure decomposes naturally over which subset of items has already been used / visited / assigned, and the problem size is small enough to make 2^n tractable: roughly n ≤ 20 for 2^n enumeration, and n ≤ ~22 for n · 2^n (the Travelling Salesman DP regime). Beyond this, the exponential explosion is fatal. The headline canonical applications are the Held-Karp algorithm for the Travelling Salesman Problem (O(n² · 2^n) exact DP), the assignment problem in O(n · 2^n) time, and set cover by full subset enumeration. A non-obvious technical gem associated with bitmask DP is the submask-iteration trick — for sub = mask; sub > 0; sub = (sub - 1) & mask — which enumerates exactly the non-empty subsets of mask in O(2^popcount(mask)) per mask, leading to a total complexity of O(3^n) rather than the naive O(4^n) over all (mask, submask) pairs. The 3^n bound, derivable in two lines from the binomial theorem, is one of the most beautiful counting arguments in algorithm design and shows up everywhere from set-cover DP to the SOS (Sum Over Subsets) DP technique used in Codeforces problems.

1. Intuition — Subsets Are Just Integers

The classical bottleneck in algorithms over subsets is representing the subsets. A Set<int> in Java costs ~50 bytes per element, supports O(1) membership only amortized over hashing overhead, and is heap-allocated — terrible for cache and for being a DP key. But for n ≤ 64, a subset S ⊆ {0, ..., n-1} fits in a single machine word: bit i is set iff element i is in S. The Set<int>’s slow operations become single CPU instructions:

Set operationBit operationCPU cost
Empty set00 cycles
Universe {0..n-1}(1 << n) - 11 cycle
Add element i`mask(1 << i)`
Remove element imask & ~(1 << i)2 cycles
Test element i(mask >> i) & 12 cycles
Union`ab`
Intersectiona & b1 cycle
Symmetric differencea ^ b1 cycle
Cardinalitypopcount(mask)1–3 cycles (hardware support)
Iterate elementsloop over set bitsO(popcount)

Using subsets as DP keys turns the DP table into an array of size 2^n, indexed directly by the integer mask. Lookup is O(1) (one array access), comparison is one integer compare, and storage is 2^n · sizeof(state) bytes — very compact. For n = 20, that’s 2^20 ≈ 10^6 entries, easily fitting in cache.

A real-world analogy: imagine a hotel with 20 rooms and you want to enumerate every possible booking pattern (which subset of rooms is occupied). Instead of writing each pattern as a list ([3, 7, 12, 19]) you write it as a 20-character string of zeros and ones (00010001000010000001), then interpret that string as a number (0x...). Same information, vastly more compact, and every “is room 7 booked?” query becomes a one-instruction test. The whole hotel-state space — over a million configurations — fits easily in memory, and you can iterate over it in a single for loop.

The intellectual leap from “DP over subsets” to “Bitmask DP” is just committing to the integer encoding. Once committed, problems whose state was naturally “which items have I used so far” become trivially indexable.

2. The Submask-Iteration Trick and the O(3^n) Identity

The most distinctive technical move in bitmask DP is iterating over the submasks of a given mask. Suppose mask has k = popcount(mask) bits set. We want to iterate over all 2^k subsets of mask (without iterating over the full 2^n integers and filtering). The idiom:

sub := mask
while sub > 0:
    process(sub)
    sub := (sub - 1) & mask
process(0)                          # don't forget the empty subset, if needed

Why this works. The expression (sub - 1) & mask decrements within the bits of mask. Subtracting 1 from sub flips its lowest set bit and sets all lower bits; the & mask zeroes out everything not in mask, so the result is the largest submask of mask strictly less than sub. Iterating from sub = mask downward visits every non-zero submask exactly once, in lexicographically descending order, and terminates at sub = 0 (which the loop condition exits before processing — handle separately if needed).

The total work to enumerate all (mask, submask) pairs over all mask ∈ [0, 2^n) is

T = Σ_{mask=0}^{2^n − 1} 2^popcount(mask)
  = Σ_{k=0}^{n} C(n, k) · 2^k                        [grouping masks by popcount]
  = (1 + 2)^n                                        [binomial theorem with x = 2, y = 1]
  = 3^n.

Symbol-by-symbol unpacking:

  • popcount(mask) is the number of set bits in mask — its cardinality as a subset.
  • 2^popcount(mask) is the number of submasks of mask.
  • C(n, k) = n! / (k! · (n-k)!) is the number of n-bit masks with exactly k bits set (choose which k positions are set).
  • The binomial identity Σ_k C(n, k) · x^k = (1 + x)^n (the binomial theorem) collapses the sum to (1 + 2)^n = 3^n.

The 3^n bound is the reason bitmask DPs that iterate over submasks are strictly faster than O(4^n) (the naive double loop over mask and submask ⊆ {0..n-1}). For n = 20, 3^20 ≈ 3.5 × 10^9 (one second of tight assembly per ~10^9 ops) — borderline; 4^20 ≈ 10^12 is hopeless. For n = 16, 3^16 ≈ 4.3 × 10^7 — fast. Many bitmask DPs sit at this 3^n complexity (set cover by full enumeration, optimal partitioning, etc.).

A combinatorial restatement: each pair (mask, submask) with submask ⊆ mask ⊆ {0..n-1} corresponds to a function f : {0..n-1} → {out, in_submask, in_mask_not_submask} — i.e., a 3-coloring. There are 3^n 3-colorings; the equivalence is bijective.

3. Tiny Worked Example — Subset Sum (LC 416 Variant)

To anchor the bitmask-DP mechanics in a concrete problem, consider Subset Sum: given nums = [3, 1, 4, 2] (n = 4), determine whether some subset sums to a target T = 6. Bitmask DP is not the optimal algorithm for this (1D DP over the sum value is O(n · T)), but it is pedagogically useful because every subset is a state.

Define dp[mask] = True iff the subset of items indicated by mask sums to exactly T. Brute force: enumerate all 2^4 = 16 masks and check.

mask (binary)itemssumdp[mask]
0000{}0False
0001{0} = {3}3False
0010{1} = {1}1False
0011{0,1} = {3,1}4False
0100{2} = {4}4False
0101{0,2} = {3,4}7False
0110{1,2} = {1,4}5False
0111{0,1,2} = {3,1,4}8False
1000{3} = {2}2False
1001{0,3} = {3,2}5False
1010{1,3} = {1,2}3False
1011{0,1,3} = {3,1,2}6True ✓
1100{2,3} = {4,2}6True ✓
1101{0,2,3} = {3,4,2}9False
1110{1,2,3} = {1,4,2}7False
1111{0,1,2,3} = {3,1,4,2}10False

There are 2 valid subsets summing to 6: {3, 1, 2} (mask 1011) and {4, 2} (mask 1100).

State transition view (what makes this DP, not just enumeration): define dp[mask] = sum of items in mask. Then dp[mask] = dp[mask ^ low_bit] + nums[index_of_low_bit], where low_bit = mask & (-mask) extracts the lowest set bit. Filling the table in order of increasing mask automatically respects the dependency (lower-popcount masks come first because each one removes one bit). Once dp is filled, dp[mask] == T is the membership check.

For more interesting bitmask DPs, the state is not a simple sum; it is “the best value achievable by using some subset and ending at a specific item” (TSP) or “the minimum cost to cover all elements in mask with some subfamily of sets” (set cover). The shape of the recurrence varies, but the index space {0, 1, ..., 2^n − 1} is the same.

4. Worked Example — Minimum Cost to Assign N Workers to N Jobs (Assignment Problem)

The Assignment Problem: given an n × n cost matrix c[i][j] representing the cost of assigning worker i to job j, find the minimum-cost perfect matching between workers and jobs (every worker gets exactly one job, every job exactly one worker).

This problem is solvable in O(n³) by the [Hungarian Algorithm], but the bitmask DP gives a cleaner O(n · 2^n) solution that is good enough for n ≤ 20.

Define dp[mask] = minimum cost to assign workers 0, 1, ..., popcount(mask) - 1 to the jobs in mask. The interpretation: we process workers in fixed order 0, 1, 2, ...; the bits of mask indicate which jobs have already been taken. Worker popcount(mask) is the next worker to assign.

Recurrence. Let i = popcount(mask). To compute dp[mask], consider the choice of which job worker i was assigned. If worker i took job j (where j ∈ mask), then before worker i’s assignment, mask was mask ^ (1 << j) (job j not yet taken), and dp of that state plus c[i][j] is the candidate.

dp[mask] = min over j in mask of: dp[mask ^ (1 << j)] + c[popcount(mask) - 1][j]

Symbol-by-symbol unpacking:

  • mask = bitmask of jobs assigned so far (bit j set ↔ job j taken).
  • popcount(mask) = number of workers assigned so far. The “current” worker (the one whose assignment we are reverse-engineering) is worker popcount(mask) - 1 (zero-indexed).
  • j ∈ mask ranges over jobs that worker popcount(mask) - 1 could have taken; for each, recurse on mask with that bit removed.
  • c[i][j] is the cost of assigning worker i to job j, looked up from the input matrix.

Base: dp[0] = 0 (no workers assigned, no cost).

Answer: dp[(1 << n) - 1] (all jobs assigned).

4.1 Tiny Numerical Example

n = 3, costs:

      job 0  job 1  job 2
w 0   3      4      6
w 1   2      5      8
w 2   7      9      1

Compute dp[mask] for mask = 0, 1, 2, ..., 7:

  • dp[000] = 0.
  • dp[001]: 1 bit, worker 0 took job 0. Cost c[0][0] = 3. dp = 0 + 3 = 3.
  • dp[010]: worker 0 took job 1. c[0][1] = 4. dp = 4.
  • dp[100]: worker 0 took job 2. c[0][2] = 6. dp = 6.
  • dp[011]: 2 bits, worker 1’s choice. Either worker 1 took job 0 (then before, mask = 010, and dp[010] + c[1][0] = 4 + 2 = 6) or job 1 (dp[001] + c[1][1] = 3 + 5 = 8). Min: 6.
  • dp[101]: worker 1 took job 0 (dp[100] + c[1][0] = 6 + 2 = 8) or job 2 (dp[001] + c[1][2] = 3 + 8 = 11). Min: 8.
  • dp[110]: worker 1 took job 1 (dp[100] + c[1][1] = 6 + 5 = 11) or job 2 (dp[010] + c[1][2] = 4 + 8 = 12). Min: 11.
  • dp[111]: 3 bits, worker 2’s choice. Either job 0 (dp[110] + c[2][0] = 11 + 7 = 18) or job 1 (dp[101] + c[2][1] = 8 + 9 = 17) or job 2 (dp[011] + c[2][2] = 6 + 1 = 7). Min: 7.

Answer: minimum cost is 7, achieved by worker 0 → job 0 (3), worker 1 → job 1 (5)? No wait — let me recompute. The optimal answer per dp[111] = 7 is: worker 2 took job 2 (cost 1), and the remaining dp[011] = 6 came from worker 0→job 1 (4) and worker 1→job 0 (2). So: w0→j1 (4) + w1→j0 (2) + w2→j2 (1) = 7. ✓

The trace is canonical bitmask DP: process workers in order, for each subset of jobs choose which job the next-to-assign worker took.

5. Pseudocode

BitmaskDP_Assignment(c, n):
    INF := infinity
    dp := array of size 2^n, all set to INF
    dp[0] := 0
    for mask := 0 to (2^n) - 1:
        if dp[mask] == INF: continue
        i := popcount(mask)
        if i == n: continue            # full assignment, done
        for j := 0 to n - 1:
            if (mask >> j) & 1 == 0:   # job j not yet taken
                new_mask := mask | (1 << j)
                cost := dp[mask] + c[i][j]
                if cost < dp[new_mask]:
                    dp[new_mask] := cost
    return dp[(2^n) - 1]

Note the forward-DP style (push from each mask to its supersets) versus the backward-DP style (pull from each mask from its subsets shown in §4). Both produce the same result; forward is sometimes cleaner for sparse-state problems.

6. Python Implementations

6.1 Assignment Problem

def min_assignment_cost(c: list[list[int]]) -> int:
    n = len(c)
    INF = float('inf')
    dp = [INF] * (1 << n)
    dp[0] = 0
    for mask in range((1 << n)):
        if dp[mask] == INF:
            continue
        i = bin(mask).count('1')      # popcount
        if i == n:
            continue
        for j in range(n):
            if not (mask >> j) & 1:
                new_mask = mask | (1 << j)
                if dp[mask] + c[i][j] < dp[new_mask]:
                    dp[new_mask] = dp[mask] + c[i][j]
    return dp[(1 << n) - 1]
 
 
# Test
c = [[3, 4, 6], [2, 5, 8], [7, 9, 1]]
print(min_assignment_cost(c))   # 7

6.2 Subset Cover (Set Cover by Full Enumeration)

Given n elements (numbered 0..n-1) and m sets (each a bitmask), find the minimum number of sets whose union is the full universe.

def min_set_cover(sets: list[int], n: int) -> int:
    full = (1 << n) - 1
    INF = float('inf')
    dp = [INF] * (1 << n)
    dp[0] = 0
    for mask in range((1 << n)):
        if dp[mask] == INF:
            continue
        for s in sets:
            new_mask = mask | s
            if dp[mask] + 1 < dp[new_mask]:
                dp[new_mask] = dp[mask] + 1
    return dp[full] if dp[full] != INF else -1

This is O(2^n · m). For exact set-cover from “best partition into rejected subsets” with submask iteration (e.g., LC 1125), the inner loop over sets becomes a submask enumeration, giving the O(3^n) complexity discussed in §2.

6.3 SOS (Sum Over Subsets) DP — The Submask-Iteration Workhorse

A classic bitmask-DP idiom: given f[mask] for every mask, compute g[mask] = Σ_{sub ⊆ mask} f[sub]. Naive: O(3^n). SOS DP: O(n · 2^n).

def sum_over_subsets(f: list[int], n: int) -> list[int]:
    g = f[:]
    for i in range(n):
        for mask in range(1 << n):
            if mask & (1 << i):
                g[mask] += g[mask ^ (1 << i)]
    return g

The trick: process bit i left-to-right, in-place. After processing bits {0, ..., i-1}, g[mask] holds the sum over all submasks differing from mask only in bits {0, ..., i-1}. After processing all n bits, g[mask] is the full sum-over-subsets. Bit-by-bit Möbius transform on the boolean lattice. Worth memorizing for advanced problems.

7. Complexity

Naive submask enumeration over all masks: O(3^n) — the identity derived in §2.

Layered bitmask DPs (assignment problem, TSP): O(n · 2^n) to O(n² · 2^n). Each subset is paired with O(n) extra state (the “current position” in TSP, or the “next worker” in assignment), and each transition is O(n) work to consider all extensions.

Practical limits.

n2^nn · 2^nn² · 2^n3^n
10102410⁴10⁵6 · 10⁴
153·10⁴5·10⁵7·10⁶1.4·10⁷
2010⁶2·10⁷4·10⁸3.5·10⁹
224·10⁶9·10⁷2·10⁹3·10¹⁰
253·10⁷8·10⁸2·10¹⁰8·10¹¹

A modern CPU sustains ~10⁹ simple operations/second. So:

  • 2^n enumeration: n ≤ 25 is fine (a second or two).
  • n · 2^n: n ≤ 22 comfortable.
  • n² · 2^n (TSP-style): n ≤ 20 borderline; n ≤ 18 fast.
  • 3^n (subset/submask): n ≤ 18 comfortable; n = 20 is ~3.5 seconds.

Space: O(2^n) for the DP table. For n = 20, that’s 4 MB for 32-bit integers, 8 MB for 64-bit. Memory is rarely the binding constraint; CPU time is.

8. Diagram — The Subset Lattice

flowchart TD
    M111["111<br/>{0,1,2}"]
    M110["110"]
    M101["101"]
    M011["011"]
    M100["100"]
    M010["010"]
    M001["001"]
    M000["000<br/>{}"]

    M111 --> M110 & M101 & M011
    M110 --> M100 & M010
    M101 --> M100 & M001
    M011 --> M010 & M001
    M100 --> M000
    M010 --> M000
    M001 --> M000

What this diagram shows. The subset lattice of {0, 1, 2} (i.e., n = 3), drawn with the full universe 111 at the top and the empty set 000 at the bottom. Each node is a 3-bit mask, labeled by both its binary representation and the set it represents. Edges go from a mask to its immediate submasks (those differing by one bit removed). The lattice has 2^n = 8 nodes, and the total number of (mask, submask) ordered pairs (the count of distinct paths from any node down to any of its descendants, including itself) is 3^n = 27. The submask-iteration trick traverses, for each starting node, the set of nodes below or equal to it; summed over all starts, this is the 3^n count. The bitmask DP fills the lattice in topological order: for forward DPs, lower-popcount masks first; for SOS DP, bit-by-bit. The DP table is essentially this lattice with a value per node, which is why DP problems with “subset” state shape map so naturally onto bitmask DP.

9. Common Interview / Competitive Problems

ProblemSourcePattern
Travelling Salesmanclassical / Held-Karp 1962dp[mask][i], O(n² · 2^n). See Travelling Salesman DP.
Assignment Problemclassicaldp[mask], O(n · 2^n)
Smallest Sufficient TeamLC 1125Set cover with skill-bitmask, O(2^n · m)
Maximum Compatibility Score SumLC 1947Bitmask matching, O(2^m · m)
Number of Ways to Wear Different HatsLC 1434Bitmask over people, iterate hats
Minimum Cost to Connect SticksLC 1167Greedy, not bitmask (included as anti-pattern)
Maximum Students Taking ExamLC 1349Row-by-row bitmask + valid configurations
Partition to K Equal Sum SubsetsLC 698dp[mask] boolean, partition correctness
Find Minimum Time to Finish All JobsLC 1723Worker × bitmask DP
Minimum Number of Refueling StopsLC 871Heap, not bitmask (anti-pattern)
Shortest Path Visiting All NodesLC 847TSP-shaped, dp[mask][node]
Beautiful ArrangementLC 526Bitmask permutation, O(n · 2^n)
Maximum AND Sum of ArrayLC 2172Bitmask of slot occupancy, O(n · 3^k)
Subset Sum problemclassical1D DP over sum, not bitmask (anti-pattern)
Set Cover (general)classicalNP-hard; bitmask DP is exact for small n

The recognition signal: the problem has a small set of items (n ≤ 20) and asks for an optimal allocation/visit/ordering whose cost depends on which items are used. If you can encode “subset of items used so far” as a bitmask and the recurrence respects subset inclusion, you have a bitmask DP.

10. Variants and Optimizations

10.1 Permutations via Bitmask DP

Counting or optimizing over permutations of a small n-element set: state = (mask, current_position), transition = choose next element from ~mask. Reduces an O(n!) brute force to O(n² · 2^n) — the Held-Karp regime. See Travelling Salesman DP.

10.2 Two-Bit-Per-Position States

Some problems need a small auxiliary state per element (e.g., “for each element, is it included, excluded, or reserved?”). Use 2n bits — a state 0 to 4^n − 1 — with the same machinery. Costs another factor of 2 in memory but is straightforward.

10.3 Profile DP (Broken-Profile DP)

For problems on a small grid (e.g., domino tiling on m × n with m ≤ ~10), the bitmask represents the profile of one row’s occupancy, and the DP transitions row-by-row. State: dp[row][mask]. Time: O(rows · 2^cols · transitions). Used in classical tilings, including Markov-chain models on small grids. See cp-algorithms profile-DP article.

10.4 Sum-Over-Supersets (Dual SOS)

Symmetrically to SOS, you can compute g[mask] = Σ_{sup ⊇ mask} f[sup] in O(n · 2^n) by processing bits left-to-right and adding from supermasks. Same idea, reversed inequality.

10.5 Subset Sum Convolution

A more advanced operation: given f, g, compute h[mask] = Σ_{a ⊕ b = mask, a ∩ b = 0} f[a] · g[b] (the subset-sum convolution) in O(n² · 2^n). Used in advanced problems like counting Hamiltonian paths in subsets. The naive computation is O(3^n); the optimized version uses Möbius transforms.

10.6 Bitset DP

When n is too big for a single integer (n > 64) but states factor over small chunks, store the DP table as a bitset (array of 64-bit integers), and use vectorized bit operations (std::bitset in C++, numpy.packbits in Python). Often gives a constant-factor 8–32× speedup; not asymptotically better.

11. Pitfalls

11.1 Forgetting to Initialize dp[0]

The empty-subset base case (dp[0] = 0 typically) must be set before the loop. Forgetting it leaves dp[0] = INF, and the entire DP returns INF.

11.2 Incorrect popcount in Forward DP

When iterating mask in increasing order in the forward style (§5), popcount(mask) indicates “how many items already used” → “the next item to consider”. An off-by-one (popcount(mask) - 1 vs popcount(mask)) is the classic bug.

11.3 Iterating Wrong Range

for mask in range(1 << n) is the standard. range(2 ** n) works in Python but allocates a giant range object in some languages. range(0, (1 << n)) with an explicit start is safe everywhere.

11.4 Submask Loop Skips Empty Subset

The idiomatic while sub > 0; sub = (sub - 1) & mask exits before processing sub = 0. If your DP needs the empty subset (e.g., partitioning into non-empty pieces with cost-of-empty = 0), handle sub = 0 explicitly after the loop.

11.5 Confusing “iterate submasks” with “iterate single bits of mask”

for j in range(n): if (mask >> j) & 1: ... iterates single bits — O(popcount(mask)) per mask, O(n · 2^n) total. The submask iteration (for sub = mask; sub > 0; sub = (sub - 1) & mask) iterates all subsets of the bits, which is O(2^popcount(mask)) per mask, O(3^n) total. These are different operations; mixing them up changes the asymptotics.

11.6 Memory Blow-Up for n > 24

2^25 = 33M cells × 4 bytes = 128 MB; usually too much. Either reduce n, use a hash map for sparse states, or rethink the algorithm. The exponential is the binding constraint; don’t try to “optimize the constant” past n = 25.

11.7 Python-Specific: bin(mask).count('1') is Slow

For very tight loops (n = 20 with O(n · 2^n) inner loops), bin(mask).count('1') is ~10x slower than C’s __builtin_popcount. Use mask.bit_count() (Python 3.10+) for a 5–10× speedup, or precompute popcount[0..2^n] array if you call popcount many times per mask.

11.8 Confusing Held-Karp Indexing

In TSP DP, dp[mask][i] requires i ∈ mask (you must end at a city you have visited). Not enforcing this in code allows invalid states to leak into the recurrence and produces wrong answers. See Travelling Salesman DP §11.

11.9 Forgetting Symmetry-Breaking for Counting Problems

Some counting bitmask DPs over-count by assigning items in different orders. Process items in fixed order (item i corresponds to bit popcount(mask) typically) to break the symmetry.

11.10 Misunderstanding “popcount” in Multi-Worker DPs

When state encodes “subset of jobs taken” and workers are processed in fixed order, the next-worker-index is popcount(mask). Some problems instead encode “subset of workers used” (then next-job-index is popcount(mask)). Be explicit about which dimension is the subset and which is the implicit order.

12. Open Questions

  • Is the 3^n submask-iteration bound tight? Yes, by the colorings argument: there are exactly 3^n ordered pairs (mask, submask) with submask ⊆ mask ⊆ {0..n-1}. Any algorithm enumerating them all is Ω(3^n).
  • When can we beat 2^n on bitmask-DP-shaped problems? Subset Sum has O(n · T) (knapsack) for small T, beating 2^n if T << 2^n. TSP has no known sub-2^n exact algorithm. Some n ≤ 30 problems benefit from meet-in-the-middle (O(2^{n/2})).
  • What’s the right cutoff for “bitmask DP” vs “MILP / SAT / general optimization”? In practice, bitmask DP is competitive only for n ≤ ~22. Beyond, modern SAT/MILP solvers with branch-and-bound dominate, even though they have worse worst-case bounds.
  • Can quantum computers do TSP faster than O(2^n · poly)? Not yet known. Grover’s algorithm gives O(√(n!)) for brute force search but no known speedup for the DP version.

12.1 TSP Exact and Approximate — As-of 2026-05

For exact metric TSP, Held-Karp’s Θ(n² · 2^n) time and Θ(n · 2^n) space remain the textbook standard (per Wikipedia: Held–Karp algorithm); no algorithm with worst-case complexity beating 2^n · poly(n) is currently known for general metric TSP. For approximation, Christofides–Serdyukov (1976) gave the long-standing 3/2-approximation for metric TSP. In 2020, Karlin, Klein, and Oveis Gharan introduced a randomized (3/2 − ε)-approximation with ε ≈ 10^{-36}, the first improvement over Christofides in more than 40 years; the paper won a best-paper award at STOC 2021 (per Wikipedia: Christofides algorithm and the STOC 2021 publication; see Quanta coverage). The improvement is mathematically dramatic but practically negligible — 10^{-36} is far below any realistic floating-point precision, so Christofides remains the engineering baseline.

13. See Also

Graph View

Backlinks