分布式子模最大化的随机组合核心集
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
提出了两种算法来有效地构建可组合核心集问题的解决方案,一种是更加实用的贪心算法,可获得 ${O (C^{k^2})}$ 的解;另一种是基于局部搜索的算法,可以获得近乎最优的解 $O (k)^{2k}$,并证明了这些算法在标准数据集上的有效性。
Jul, 2019
本研究证明,匹配问题和点覆盖问题在同时通信模型中的不可承受性根源于基础图形跨机器的对抗性分区,进而展示这两个问题存在随机组分的可组合核的对数 O (n)。
May, 2017
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
本文介绍了两种在 MapReduce 模型中的基数约束子模规划的简单算法,第一种算法在 2 个 MapReduce 轮中可以实现 1/2 的近似度,第二种算法可以在 1+o (1)/ε 个 MapReduce 轮中实现 1−1/e−ε 的近似度。
Oct, 2018
本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题,建立了离散问题和连续松弛之间的强联系,并利用这种联系提出了近似算法和确定性技术,得到了很好的解决方案。
Jan, 2011