Improved Approximation Ratios for Multiway Cut
Statement
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).
Record
- Source
- Added
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
computation · #1
Joshua Brakensiek, Neng Huang, Aaron Potechin and Uri Zwick, using ChatGPTThat credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
"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."
Record bounds on the ratio; the exact approximability of Multiway Cut remains open.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.