Jun, 2016
近线性时间内的几何中位数
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, Aaron Sidford
TL;DR本文提供了计算几何的一个传统优化问题中，几何中位数的解决方案，证明了可以使用长步内点法和随机次梯度下降法来获得快速准确的解决方案，此结果超过了传统内点方法的理论界限，此方法希望为将来的类似问题提供启示。
Abstract
In this paper we provide faster algorithms for solving the geometric median
problem: given $n$ points in $\mathbb{R}^{d}$ compute a point that minimizes
the sum of Euclidean distances to the points. This is one of the oldest
non-trivial problems in →
geometric mediancomputational geometryinterior point methodstochastic subgradient descentoptimization problem
发现论文，激发创造
介于 $k$- 中位数和 $k$- 中心点之间的插值算法：针对有序 $k$- 中位数的近似算法
研究了一种叫做有序 k - 中位数的问题，并提出了一种（18+ε）- 近似算法，该算法结合了广义松弛和原始对偶模式，并使用了 Aouad 和 Segev 的枚举过程。对于特殊情况的 {0,1} 权重，提出了一种新颖的规约方法，并得到了一个干净简洁的（8.5+ε）- 近似算法。
Nov, 2017
离散几何空间中鲁棒聚类的参数化逼近
本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。
May, 2023
通过伪近似算法逼近 $k$- 中位数
该研究提出了一种新颖的近似算法，在 K - 中位数中实现了 1+sqrt（3）+ epsilon 的近似保证，该方法基于两个组件，第一个是关于伪近似算法的，第二个是关于 K 个设施的。
Nov, 2012
欧几里得 k - 均值问题的近似难度
本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。
Feb, 2015
通过迭代取整实现 $k$- 中位数和 $k$- 均值异常值的常数近似
本论文介绍了一个新的迭代舍入框架并用于许多聚类问题的近似算法，该算法可以大幅改善现有算法的近似比，并且通过前处理程序将几乎积分解转换为完全积分解。
Nov, 2017