均匀最稀疏割的近平方根对数积分间隙
Near-square-root logarithmic integrality gaps for uniform sparsest cut
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究均匀最稀疏割问题的Goemans–Linial半正定松弛积分间隙。作者构造了一列n趋于无穷的实例，需求为每对不同顶点之间为一、容量为非负实数，声称其积分间隙至少为c√(log n)/(log log n)^3。摘要表示这与Arora–Rao–Vazirani上界在log log n的幂次范围内相匹配。材料仅提供摘要，未给出构造细节与独立验证。
- 构造均匀最稀疏割实例，需求为每对不同顶点间为一。
- 作者声称Goemans–Linial积分间隙至少为c√(log n)/(log log n)^3。
- 该下界与Arora–Rao–Vazirani上界相差log log n的幂次。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least $`c\sqrt{\log n}/(\log\log n)^3`$ along a sequence $`n\to\infty`$. The demand is one between every pair of distinct vertices, and the capacities are nonnegative real numbers. This matches the Arora–Rao–Vazirani upper bound up to a power of $`\log\log n`$.
用户标记：未标记
固定编号：9d5795100c165b60
原文来源