Jun, 2014

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

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

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

    Nov, 2017

  • 完全图和完全 k 部分图上相关聚类的近似最优线性规划舍入算法

    该论文提出了一种新的线性规划松弛四舍五入方案，解决了相关聚类问题的近似算法问题和完整性间隙问题，从而在完全图中实现了 2.06-ε 的近似度，而在完全 $k$- 部分图中实现了 3 的近似度。

    Dec, 2014

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

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

    Nov, 2012

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

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

    Nov, 2017

  • 多项式对数轮次内求解相关聚类问题的三因素近似算法失效

    本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

    Jul, 2023

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

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

    Nov, 2017

  • 基于稳定中位数的自适应估计器泛化

    本文主要介绍了一种基于近似中位数算法的算法来估算统计数据集的普适性，该算法满足差分隐私的强稳定性保证，解决了统计数据集在自适应问题上的泛化保证的新方法。

    Jun, 2017

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

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

    May, 2024

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

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

    Jun, 2022

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

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

    May, 2023