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

CREATORNairen CaoVincent Cohen-AddadEuiwoong LeeShi Li David Rasmussen LolckAlantha NewmanMikkel ThorupLukas VoglShuyi YanHanwen Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE164 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20883

Browse the full library · About the Tower of Babel