跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1295新增论文
+1026其中 AI 相关
+111已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-17 04:58 · 全站最近入库:2026-11-17 16:10各信源进度 →

统计口径与数据新鲜度

统计 2026-11-16 16:56 — 2026-11-17 16:56(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 16:10库内论文最新更新时间:2026-11-17 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

25,122 已收录论文20,967 AI 相关7,309 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
版本更新 · v2arXiv:2609.35453

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

David García-Soriano, Atsushi Miyauchi

原文摘要

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(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ 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). 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$. On the hardness side, we show that approximating Maxagree within $0.802+ε$ is Unique Games-hard via a construction in Gaussian space analyzed by Borell's inequality.

cs.DS