Nov, 2017

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

PDF
TL;DR本论文介绍了一个新的迭代舍入框架并用于许多聚类问题的近似算法，该算法可以大幅改善现有算法的近似比，并且通过前处理程序将几乎积分解转换为完全积分解。
clustering problemsiterative rounding frameworkapproximation algorithmslp integrality gappre-processing procedure
发现论文，激发创造
  • 有序 k - 中位数的常系数近似

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

    Nov, 2017

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

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

    Jun, 2022

  • k-Median 问题的改进近似算法，以及预算优化中的正相关性

    介绍了一个算法，它在依赖取整方案中保证依赖取整的已知特性，对于变量的 "小" 子集具有近似最优的行为，同时显式地处理正相关性，并将李和斯文森在经典 k - 中位数问题的近似比从 2.732+ϵ 改进到 2.675 + ϵ，时间复杂度从 N^{O (1/ϵ^2)} 变为 N^{O ((1/ϵ) log (1/ϵ))}。

    Jun, 2014

  • 通过伪近似算法逼近 $k$- 中位数

    该研究提出了一种新颖的近似算法，在 K - 中位数中实现了 1+sqrt（3）+ epsilon 的近似保证，该方法基于两个组件，第一个是关于伪近似算法的，第二个是关于 K 个设施的。

    Nov, 2012

  • 可解释聚类的近似最紧算法

    本文研究了一个最近提出的可解释聚类框架，专注于 k-medians 和 k-means 问题，并提供了近似算法和上下界。

    Jul, 2021

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

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

    Nov, 2017

  • 带有大量噪音数据的分布式 k - 聚类

    在分布式环境中，对 $k$-center/median/means 聚类与 outliers 问题 (或 $(k, z)$-center/median/means 问题) 进行研究，提出了一种改进算法，能够更好地解决 communication costs 线性依赖于 outliers 数量的问题。

    Oct, 2018

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

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

    May, 2023

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

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

    Jun, 2021

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

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

    Jun, 2021