NeFut Logo NeFut
EN 管理员登录

[算法理论] Bourgain 定理在欧几里得度量空间并的推广

发布于:2026-11-09 22:00 最后更新:2026-11-12 00:51
#algorithm #optimization #Math

我们研究将 $k$ 个欧几里得集合的并嵌入到欧几里得空间时的失真上界。主要结果表明,无论点的数量多少,任意 $k$ 个欧几里得集合的并都可以以至多 $O\big(k^{1.128}\log k\big)$ 的失真嵌入到欧几里得空间。这比之前通过迭代 Makarychev 与 Makarychev (2016) 在 $k=2$ 的特殊情形得到的 $2^{O(k)}$ 上界提升了指数级。进一步,如果额外假设每个欧几里得集合在加入任意另外两点后仍保持欧几里得性质,则可以得到 $O(\log k)$ 的失真上界,并且该上界在渐近意义上是紧的,从而得到对 Bourgain (1985) 定理的一个自然推广。我们还证明,整体失真可以被上界为 $O(\log k)$ 与各个欧几里得集合的 Lipschitz 延拓常数最大值的乘积。\n\n点评:本文在度量嵌入理论中实现了从指数级到多项式级的显著改进,并在额外几何假设下恢复了经典的对数失真界,提供了对 Bourgain 定理的有力扩展。

原文链接: https://arxiv.org/abs/2611.08546

[h] 返回首页