A (log n)^(Ω(1)) integrality gap for the Sparsest Cut SDP
read the original abstract
We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap $(\log n)^{\Omega(1)}$. This is achieved by exhibiting $n$-point metric spaces of negative type whose $L_1$ distortion is $(\log n)^{\Omega(1)}$. Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to $L_1$ when restricted to cosets of the center.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Performance Isolation and Semantic Determinism in Efficient GPU Spatial Sharing
CoGPU resolves the tradeoff in GPU sharing by introducing GPU coroutines for semantic-preserving resource migration, delivering up to 79.2% higher training throughput and zero token mismatch in inference.
-
FlexPipe: Adapting Dynamic LLM Serving Through Inflight Pipeline Refactoring in Fragmented Serverless Clusters
FlexPipe introduces runtime pipeline refactoring for LLMs to achieve higher resource efficiency and lower latency in serverless GPU clusters with fragmentation.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.