TY - GEN
T1 - Handling Correlated Rounding Error via Preclustering
T2 - 64th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2023
AU - Cohen-Addad, Vincent
AU - Lee, Euiwoong
AU - Li, Shi
AU - Newman, Alantha
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - We consider the classic correlation clustering problem: Given a complete graph where edges are labelled either + or -, the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] gave a 1.995-approximation for the problem using the Sherali-Adams hierarchy, hence beating the integrality gap of 2 of the classic linear program. We significantly improve upon this result by providing a 1.73-approximation for the problem. Our approach brings together a new preprocessing of correlation clustering instances that enables a new LP formulation which combined with the algorithm from [CLN22] yields the improved bound.
AB - We consider the classic correlation clustering problem: Given a complete graph where edges are labelled either + or -, the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] gave a 1.995-approximation for the problem using the Sherali-Adams hierarchy, hence beating the integrality gap of 2 of the classic linear program. We significantly improve upon this result by providing a 1.73-approximation for the problem. Our approach brings together a new preprocessing of correlation clustering instances that enables a new LP formulation which combined with the algorithm from [CLN22] yields the improved bound.
KW - LP-hierarchies
KW - Sherali-Adams
KW - approximation algorithms
KW - clustering
UR - https://www.scopus.com/pages/publications/85178445950
U2 - 10.1109/FOCS57990.2023.00065
DO - 10.1109/FOCS57990.2023.00065
M3 - Conference contribution
AN - SCOPUS:85178445950
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1082
EP - 1104
BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PB - IEEE Computer Society
Y2 - 6 November 2023 through 9 November 2023
ER -