介于 $k$- 中位数和 $k$- 中心点之间的插值算法：针对有序 $k$- 中位数的近似算法

Nov, 2017

介于 $k$- 中位数和 $k$- 中心点之间的插值算法：针对有序 $k$- 中位数的近似算法

Interpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median

Deeparnab Chakrabarty, Chaitanya Swamy

TL;DR研究了一种叫做有序 k - 中位数的问题，并提出了一种（18+ε）- 近似算法，该算法结合了广义松弛和原始对偶模式，并使用了 Aouad 和 Segev 的枚举过程。对于特殊情况的 {0,1} 权重，提出了一种新颖的规约方法，并得到了一个干净简洁的（8.5+ε）- 近似算法。

Abstract

We consider a generalization of $k$-median and $k$-center, called the {\em ordered $k$-median} problem. In this problem, we are given a metric space $(\mathcal{D},\{c_{ij}\})$ with $n=|\mathcal{D}|$ points, and a non-increasing weight vector $w\in\mathbb{R}_+^n$, and the goal is to open $k$ centers and assign each point each point $j\in\mathcal{D}$ to a cent

ordered k-median approximation algorithm primal-dual schema lagrangian relaxation reduction

发现论文，激发创造

有序 k - 中位数的常系数近似

提供了一种基于 LP-rounding 的近似算法来解决有序 k-Median 问题，并探讨了包括权重和距离分配方法在内的多种算法来处理该问题。

Nov, 2017

图上 k - 中心问题的动态算法

提供了首个对动态图进行边更新的 k - 中心问题的高效算法

Jul, 2023

更好的面向个体公平的 $k$- 聚类算法

运用线性规划和局部搜索算法解决在数据聚类问题中，$\ell_p$-range 目标下的个体公平问题。通过修改 LP 理论和结合局部搜索算法实践，实现更优算法，并在实验中展现了出众的表现。

Jun, 2021

个体公平聚类的改进近似算法

此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

Jun, 2021

通过迭代取整实现 $k$- 中位数和 $k$- 均值异常值的常数近似

本论文介绍了一个新的迭代舍入框架并用于许多聚类问题的近似算法，该算法可以大幅改善现有算法的近似比，并且通过前处理程序将几乎积分解转换为完全积分解。

Nov, 2017

离散几何空间中鲁棒聚类的参数化逼近

本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

May, 2023

对成对公平 $k$- 中位聚类问题的多项式时间近似

我们研究了配对公平聚类，其中对于每个聚类和每个组，来自组 i 的聚类 C 中的点的数量必须不超过其他组 j 中的点的数量的 t 倍，我们设计了第一个满足公平性约束条件的多项式时间近似算法，并提供了近似难度的结果。

May, 2024

近线性时间内对倍增度量聚类的近似算法

针对度量空间中的经典设施定位、$k$- 中位数和 $k$- 均值问题，我们提供了近线性时间的逼近方案，并展示了针对各种变型问题的技术扩展。

Dec, 2018

公平范围聚类的近似算法

研究公平间距聚类问题，提供 O (1) 的近似算法在最多 k+2l 个中心中选择最小化聚类成本的一组中心，并仅在每个人口统计上最多违反 2 个加法项的上限。

Jun, 2023

社会公平的常积分因子 $k$- 聚类近似算法

本研究对含 m 个群体的社会公平 (l_p, k)- 聚类问题的近似算法进行研究，其中特殊情况包括社会公平 k - 中心 (p=1) 和社会公平 k - 均值 (p=2) 问题。研究分别给出了多项式时间和两种不同的 (n^{2^{O (p)} m^2} 和 k^m poly (n)) 的近似算法，并探讨了这些算法与现有算法的比较。

Jun, 2022