TY - GEN
T1 - Optimal Rounding for Sparsest Cut
AU - Chang, Alan
AU - Naor, Assaf
AU - Ren, Kevin
N1 - Publisher Copyright:
© 2025 Owner/Author.
PY - 2025/6/15
Y1 - 2025/6/15
N2 - We prove that the integrality gap of the Goemans-Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is (λlogn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,yϵ M with d(x,y)≥ τ, the probability that both xϵ Z and d(y,Z)≥ βτ/λ1+log(|B(y,κ β τ)|/|B(y,β τ)|) is ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora-Rao-Vazirani rounding technique.
AB - We prove that the integrality gap of the Goemans-Linial semidefinite program for the Sparsest Cut problem (with general capacities and demands) on inputs of size n≥ 2 is (λlogn). We achieve this by establishing the following geometric/structural result. If (M,d) is an n-point metric space of negative type, then for every τ>0 there is a random subset Z of M such that for any pair of points x,yϵ M with d(x,y)≥ τ, the probability that both xϵ Z and d(y,Z)≥ βτ/λ1+log(|B(y,κ β τ)|/|B(y,β τ)|) is ω(1), where 0<β<1<κ are universal constants. The proof relies on a refinement of the Arora-Rao-Vazirani rounding technique.
KW - metric embeddings
KW - semidefinite programming
KW - Sparsest Cut problem
UR - https://www.scopus.com/pages/publications/105009827792
UR - https://www.scopus.com/inward/citedby.url?scp=105009827792&partnerID=8YFLogxK
U2 - 10.1145/3717823.3718285
DO - 10.1145/3717823.3718285
M3 - Conference contribution
AN - SCOPUS:105009827792
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 643
EP - 652
BT - STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing
A2 - Koucky, Michal
A2 - Bansal, Nikhil
PB - Association for Computing Machinery
T2 - 57th Annual ACM Symposium on Theory of Computing, STOC 2025
Y2 - 23 June 2025 through 27 June 2025
ER -