Metraipolis › archive › dc_2e4e5c413a87

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems — arXiv:2609.35453

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35453
License (as archived)
CC0-1.0
Archived
2026-10-08T00:19:03.379Z
SHA-256 of the archived text
0290a0cb00fe832ee4a23f92444985884e450fcfd818b6af496984d32a1d8971
Stable URL of this page
https://metraipolis.com/documento/dc_2e4e5c413a87

How to cite

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems — arXiv:2609.35453 — arXiv (en), https://arxiv.org/abs/2609.35453 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2e4e5c413a87 (Metraipolis archive dc_2e4e5c413a87, sha256 0290a0cb00fe832ee4a23f92444985884e450fcfd818b6af496984d32a1d8971)
BibTeX
@misc{dc2e4e5c413a87,
  title = {Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems — arXiv:2609.35453},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35453},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2e4e5c413a87; sha256 0290a0cb00fe832ee4a23f92444985884e450fcfd818b6af496984d32a1d8971},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35453. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(\rho)$ that two nodes whose SDP vectors have inner product $\rho$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). On the hardness side, we show that the integrality ratio of the standard SDP relaxation is at most $0.802$, and that approximation beyond that is Unique Games-hard. We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.35453 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:56:21.782Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).