Improved Approximation Ratios for Multiway Cut
New upper and lower bounds on the approximation ratio achievable for Multiway Cut via large mixtures of new and old rounding schemes for the CKR relaxation, advancing the ratio ladder that has run since Călinescu-Karloff-Rabani (1998).
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Computation
- Field
- Approximation algorithms
- Posed by
- —
- Year posed
- —
- Years open
- —
- Solved
- 2026-03-30
- Model
- ChatGPT
- Vendor
- OpenAI
- Collaborators
- Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Record bounds on the ratio; the exact approximability of Multiway Cut remains open.
What the AI did
"We acknowledge help from ChatGPT while writing the code for discovering new rounding schemes and while preparing some of the plots. We emphasize that we did not use ChatGPT or any other LLM model while writing our verification code."