May, 2023

约束 k 次模最大化的在线和流式算法

PDF
TL;DR本文提出了单遍流式和在线算法的受约束 k - 次模最大化，其中包含基数和背包约束限制，该算法可以提供不错的近似解和高效的解决方案，并在广告分配等应用实例上得到了验证。
constrained k-submodular maximizationstreaming algorithmsonline algorithmsconstant-factor approximation guaranteesad allocation
发现论文，激发创造
  • 满足背包约束的敌对鲁棒次模最大化

    该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

    May, 2019

  • 做更少，得更多：带子采样的流式子模最大化

    该论文提出了首个一次遍历的流算法，用于求解子模最大化问题，采用数据采样，能够在各种情况下获得最紧密的逼近保证，同时具有最小的内存占用和对函数评估数量的最低要求，试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上

    Feb, 2018

  • 流式非单调子模最大化：实时个性化视频摘要

    本文提出了第一个高效的单遍流式计算算法 Streaming Local Search，用于在独立系统和多重背包约束下，同时最大化非单调子模函数，解决实时提取和总结大规模视频流的问题。

    Jun, 2017

  • 全息子模流处理：紧密逼近、最小内存和低自适应复杂度

    本文讨论了在 streaming setting 下最大化单调次模函数，并给出了一种新的算法 Sieve-Streaming++ 以及其扩展到多源 streaming setting 的方案，最终将该算法应用于 twitter 和 youtube 视频的多源数据摘要任务中进行效率测试。

    May, 2019

  • 子模函数最大化的流式算法

    该研究主要针对单次流式处理的情况下，最大化一个非负子模集函数 f 编制一些确定性和随机算法，以实现对 p 匹配约束条件的大约 1 /p 的逼近，假设具有时间和资源约束。

    Apr, 2015

  • 非单调次模最大化的实用并行算法

    非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近

    Aug, 2023

  • 从数据流中公平且代表性地选择子集

    本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题，并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。

    Oct, 2020

  • 针对背包约束的快速自适应非单调子模型最大化

    本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法，该算法实现了 5.83 近似和 O (nlogn) 时间复杂度；并将其转移到随机版本的问题，得到了首个非单调目标的常数近似，实验表明该方法在实际和合成数据上的性能得到了改进。

    Jul, 2020

  • 在 Matroid 约束下流式子模最大化中的公平性

    论文研究流式子模最大化算法中公平性的应用，提出了针对劣模最大化算法的公平机器学习算法，包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后，通过社会网络中的最大覆盖，电影推荐和样本聚类等应用的实验验证了其有效性。

    May, 2023

  • 结构稳健次模最大化：离线与在线算法

    本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法，旨在提高对次模优化的建模范围，尤其应用于单个或多个基序，背包以及具有分散鲁棒性的标准约束条件，该算法适用于离线和在线设置，并且在线问题的双标准解决方案具有 sub-linear 的遗憾。

    Oct, 2017