Approximation ratio for Multiway Cut
the best proved approximation ratio for Multiway Cut with arbitrarily many terminals
- steps
- 5
- by AI
- 0
- since
- 1992
The line is the frontier over time, falling as the bound comes down: lower is better here. Filled dots are steps that moved it; muted dots are results that did not. Orange dots are catalog entries, results with AI in the loop. Hollow dots are candidates under review and never move the line.Grey dots along the top edge are results from before the quantity had a number, placed at the worst end because they have no value on this axis. Dots that would overlap are nudged sideways a few pixels. Hover a dot for its value and attribution.
About this frontier
Given a weighted graph and terminals, Multiway Cut asks for the cheapest set of edges whose removal separates every terminal from every other. It is APX-hard for , so the question is the best polynomial-time approximation ratio. Dahlhaus, Johnson, Papadimitriou, Seymour and Yannakakis gave in 1992; the linear-programming relaxation of Calinescu, Karloff and Rabani (1998) brought it to , and every step since has been a new way of rounding that one relaxation: , , in 2014, and in 2026 from a computer-found mixture of hundreds of rounding schemes. Under the Unique Games Conjecture the true answer is the relaxation's integrality gap, known to be at least ; the gap between and that floor is the frontier.
Every step, newest first
| Date | Value | Who | Model | Status | Source |
|---|---|---|---|---|---|
| 30 Mar 2026 | A generalised Kleinberg-Tardos rounding replaces exponential clocks, and the algorithm is a computationally discovered mixture of hundreds of rounding schemes rather than two to four. Analysis by analytic bounds plus interval arithmetic; also the first small-k improvements in 25 years. Unreviewed arXiv v1, not rerun here: a candidate. | Brakensiek, Huang, Potechin and Zwick, with ChatGPT | ChatGPT | candidate unreviewed | entry |
| 2014 | best Descending thresholds added to the mix. An analytic 1.3022 and, with independent thresholds too, a computer-assisted 1.2965. STOC 2014. The record for twelve years; Buchbinder, Schwartz and Weizman's analytic 297/229 = 1.29694 (2021) came close without passing it. | Ankit Sharma and Jan Vondrak | – | historical | source ↗ |
| 2013 | Exponential clocks: a simple 4/3 - 4/(9k-6) algorithm and a slightly more complicated 1.3239 - 1/(24k). STOC 2013. | Niv Buchbinder, Joseph Naor and Roy Schwartz | – | historical | source ↗ |
| 1999 | Single threshold mixed with independent thresholds. STOC 1999; Mathematics of Operations Research 29 (2004). Also the exact 12/11 for k = 3, and small-k ratios that stood until 2026. | Karger, Klein, Stein, Thorup and Young | – | historical | source ↗ |
| 1998 | The relaxation everything since rounds: embed the terminals at the vertices of a simplex, relax, and cut with a single random threshold. STOC 1998; JCSS 60 (2000). Under Unique Games its integrality gap is the true approximability. | Gruia Calinescu, Howard Karloff and Yuval Rabani | – | historical | source ↗ |
| 1992 | The complexity of multiterminal cuts: NP-hardness for k >= 3 and a combinatorial 2 - 2/k approximation from isolating cuts. STOC 1992; SIAM Journal on Computing 23 (1994). | Dahlhaus, Johnson, Papadimitriou, Seymour and Yannakakis | – | historical | source ↗ |
Every value is from Table 1 of the 2026 paper, which lists the arbitrary-k ladder with method and analysis type, read here; conference dates are the row dates. Sharma and Vondrak 2014 has an analytic 1.3022 and a computational 1.2965 and is one row at the better number; Buchbinder, Schwartz and Weizman's analytic 297/229 (2021) is a near-miss, not a step, and is not drawn. The 1.20016 floor is a Unique-Games-conditional bound from the integrality gap (Berczi, Chandrasekaran, Kiraly and Madan 2020), checked rather than drawn. The 2026 row is a candidate: unreviewed arXiv v1, not rerun here.