Solving the Correlation Cluster LP in Sublinear Time
Nairen CaoVincent Cohen-AddadEuiwoong LeeShi Li David Rasmussen LolckAlantha NewmanMikkel ThorupLukas VoglShuyi YanHanwen Zhang · 2025
Read Solving the Correlation Cluster LP in Sublinear Time by Nairen CaoVincent Cohen-AddadEuiwoong LeeShi Li David Rasmussen LolckAlantha NewmanMikkel ThorupLukas VoglShuyi YanHanwen Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20883.txt.
Description
Nairen Cao and co-authors solve a giant planning puzzle behind correlation clustering in near-linear time, in a 2025 paper. The puzzle sorts items so that alike pairs sit together and unlike pairs split, at least total cost. A recent linear program frames it tightly, but with a variable for every possible group, an exponential sprawl. Past solvers tamed it only at heavy polynomial cost.
Their new route finds a near-best plan for that program in time that grows almost with the input's length alone, times a factor set by the allowed slack. The same clock covers the rounding that turns the plan into a true clustering, with a proven quality bound. The speed closes a gap between the sharpest known approximations and the fast algorithms lately in fashion. The authors credit a fresh way of handling the sprawl: work with the program's shadow, not its full body.
Catalog record
| CREATOR | Nairen CaoVincent Cohen-AddadEuiwoong LeeShi Li David Rasmussen LolckAlantha NewmanMikkel ThorupLukas VoglShuyi YanHanwen Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 164 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-20883