Nov, 2017

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

PDF
TL;DR提供了一种基于 LP-rounding 的近似算法来解决有序 k-Median 问题，并探讨了包括权重和距离分配方法在内的多种算法来处理该问题。
ordered k-median problemapproximation algorithmslp-roundingweight bucketingdistance bucketing
发现论文，激发创造
  • 介于 $k$- 中位数和 $k$- 中心点之间的插值算法：针对有序 $k$- 中位数的近似算法

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

    Nov, 2017

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

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

    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

  • 最小范数和有序优化问题的近似算法

    本文研究最小范数优化问题，通过引入常用的单调对称范数，相较于已有的算法，针对负载均衡和聚类等实际问题，提出了一套通用且高效的解决方案，并在此基础上给出了一些近似算法。

    Nov, 2018

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

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

    Nov, 2012

  • 近似聚类的最优时间界限

    本文研究了基于 k-median 目标函数的聚类问题，提出了一种称为连续采样的简单但有效的采样技术，并使用该技术开发了一个可在 O（nk）时间内运行的算法来解决 k-median 问题。

    Dec, 2012

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

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

    May, 2023

  • 设施选址问题中局部搜索算法的简化分析

    本文研究了度量实例的本地搜索算法，针对设备位置问题：无容量设备位置问题（UFL），以及 $k$-median，$k$-center 和 $k$-means 的无容量版本。

    Sep, 2008

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

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

    Dec, 2018

  • 利用 MapReduce 进行快速聚类

    本文考虑在 MapReduce 环境下设计用于处理大数据集的聚类算法，重点研究实用和流行的聚类问题，如 k-center 和 k-median，并开发具有常数因子近似保证的快速聚类算法。

    Sep, 2011