Max Cut with Small-Dimensional SDP Solutions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914475900141568 |
|---|---|
| author | Chang, Hsien-Chih Ghoshal, Suprovat Lee, Euiwoong |
| author_facet | Chang, Hsien-Chih Ghoshal, Suprovat Lee, Euiwoong |
| contents | We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $α_{GW}\approx 0.87856$, it is natural to ask whether one can beat $α_{GW}$ when the SDP solution lives in $\mathbb{R}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(α_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_13971 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Max Cut with Small-Dimensional SDP Solutions Chang, Hsien-Chih Ghoshal, Suprovat Lee, Euiwoong Data Structures and Algorithms We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $α_{GW}\approx 0.87856$, it is natural to ask whether one can beat $α_{GW}$ when the SDP solution lives in $\mathbb{R}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(α_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections. |
| title | Max Cut with Small-Dimensional SDP Solutions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.13971 |