Aug, 2023

非单调顺序次模最大化

PDF
TL;DR研究论文中，我们探讨了序列次模优化的基本问题，针对从一个给定集合中选择和排序 k 个项目的场景，最大化 k 个（可能非单调的）次模函数的加权求和，其中每个函数 f_j 将序列中的前 j 个项目作为输入。不同于过去关于单调情形的研究，本文首次考虑了具有非单调次模函数的问题，并提出了对于灵活和固定长度约束以及具有相同效用函数的特殊情况的有效解决方案。通过视频推荐领域的实证评估，我们提出的算法的有效性得到了验证。这项研究的结果对推荐系统和组合优化等多个领域具有重要意义，其中项目的排序对于整体价值具有显著影响。
sequential submodular maximizationnon-monotone submodular functionsrecommendation systemsflexible and fixed length constraintsvideo recommendations
发现论文，激发创造
  • 动态非单调次模最大化

    我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数，肯定回答了陈和彭提出的问题，并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解，并且每次更新使用预期平摊的 O (ε^-3 * k^3 * log^3 (n) * log (k)) 或者 O (ε^-1 * k^2 * log^3 (k)) 的预言查询。此外，我们展示了我们的动态算法在视频概述和基于几个真实数据集的最大割问题上的优势。

    Nov, 2023

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

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

    Jul, 2020

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

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

    Aug, 2023

  • 满足拟阵和背包约束的非单调次模最大化

    本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化，同时满足多个基数约束或背包约束，特别是在 k 个划分拟阵约束下，改进了以前已知的最佳保证，获得了（1 /k+1 + 1 /k-1 + ε）的近似保证。

    Feb, 2009

  • 具近似最优适应性和查询复杂度的非单调次模最大化

    研究分布式情况下近似最大化非单调子模函数时算法适应性和查询复杂度的方法及其应用

    Aug, 2018

  • 具背包约束的单调和非单调次模最大化的近似算法

    本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题，建立了离散问题和连续松弛之间的强联系，并利用这种联系提出了近似算法和确定性技术，得到了很好的解决方案。

    Jan, 2011

  • 超越单调性的数据摘要：非单调两阶段子模最大化

    针对两阶段子模问题，使用提供的子模训练函数减少底层集合，以确保优化新的目标函数能在减少后的底层集合上获得与原始底层集合相当的结果。本研究突破性地将非单调子模函数引入此领域，并提出了首个常数因子近似算法。

    Sep, 2023

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

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

    Jun, 2017

  • 小批量次模最大化

    我们提出了第一个用于最大化非负单调可分解次模函数的小批量算法，在一组约束条件下。我们在理论和实践上都优于基于稀疏化方法的方法。我们在实验中观察到，我们的算法生成的解比基于稀疏化方法生成的解要好得多。

    Jan, 2024

  • 子模量极大化的 FAST 算法

    本篇论文介绍了一种新算法 FAST，旨在通过最大化满足劣模性的子模函数，使逼近比例任意接近 1-1 /e，由 O (log（n）log^2 (log k)) 次适应，总共使用 O（nloglog (k)) 次查询，在处理大数据集方面，该算法的查询复杂度和轮数都非常高效，且实验证明，FAST 比最先进的串行算法甚至是并行化的经过超级优化的状态算法都快得多。

    Jul, 2019