摘要
几何中位数问题旨在寻找一个点在 $\mathbb{R}^d$ 中，使得其到输入集的欧几里得距离之和最小。这是计算几何中的经典问题，并在众多优化任务中出现，许多任务要求解决方案满足额外的结构约束。减少输入规模的常见方法是构造核心集，核心集是一个小的加权子集，能够真实地代表特定优化问题的输入。
强核心集保留每个候选解的成本，但需要线性时间构造；而弱核心集允许亚线性构造，通过均匀采样实现，但仅保留近似最优解，这在解决受约束的问题时是不够的。为了解决这个问题，我们关注最近提出的“稳定核心集”这一中间概念，它能够同时处理所有约束变体。目前，已知的稳定核心集和弱核心集的样本大小之间存在较大差距。
我们的主要结果是，大小为 $O(\epsilon^{-2} \log \tfrac{1}{\epsilon})$ 的均匀样本是几何中位数的稳定 $(\epsilon, O(\epsilon))$-核心集，且具有较高的常数概率，这个界限在对数因子上是紧的。我们的分析适应了 Carmel 和 Krauthgamer（ICLR 2026）构造稳定核心集的最新方法，涉及 $O(\log d)$ 的因子。我们展示了一种迭代论证，逐步减少样本大小，并消除了对维度 $d$ 的依赖。从高层次看，这种方法类似于强核心集的迭代大小减少技术，但不适用于弱核心集。
博主点评： 本文通过均匀采样提出了一个新的稳定核心集构造方法，显著降低了样本数量的需求，并为处理约束问题提供了有效的解决方案。这一研究为计算几何领域提供了重要的理论支持，值得关注。