均匀最稀疏割的常数因子硬度
Constant-factor hardness of uniform sparsest cut
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究均匀最稀疏割问题的近似硬度。作者声称证明：对每个固定常数 C>1，在因子 C 内近似均匀最稀疏割是 NP-难的。所构造的输出图具有非负有理容量，且每对不同顶点之间具有单位需求。研究意义在于给出均匀最稀疏割问题的常数因子 NP-硬度下界。
- 对每个固定 C>1，证明因子 C 内近似均匀最稀疏割是 NP-难的。
- 输出图具有非负有理容量。
- 每对不同顶点之间具有单位需求。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that, for every fixed C > 1, approximating Uniform Sparsest Cut within factor C is NP-hard. The output graphs have nonnegative rational capacities and unit demand between every pair of distinct vertices.
用户标记：未标记
固定编号：d4749b7789675253
原文来源