Sep, 2018

带有短列表的次模秘书问题

PDF
TL;DR本文提出了一种称为 submodular k-secretary problem with shortlists 的问题设置，旨在改善 submodular k-secretary 问题的可达竞争比率，而使用大小为 O (k) 的 shortlist，我们证明了该算法可以保证任意常数 ε>0 的竞争比率为 1-1/e-ε-O (k^-1)。我们还证明了，在 m-submodular 函数的特殊情况下，使用 O (1) 的 shortlist，我们的算法可以保证 ε>0 的竞争比率为 1-ε。最后，我们还证明了我们的算法可以在流处理模型中实现，并且可以通过使用大小为 O（k）的内存缓冲区来保证子模函数最大化的 1-1/e-ε-O (k^-1) 逼近，这大大提高了以前已知的逼近因子。
发现论文，激发创造
  • k 秘书问题的新结果

    该论文研究了 $k$- 秘书问题，提出了一种自然的确定性算法，其竞争比率均高于 $1 /e$，并针对 $ k $ 较小的情况进行了分析。

    Dec, 2020

  • 在线子模最大化算法及其中断

    本文研究基于在线变体的子模函数最大化问题，探讨了两种特殊情况并得出了竞争比的上下界。具体而言，设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。

    Jan, 2015

  • 鲁棒的单调次模函数最大化

    研究了具有健壮性约束的基数约束单调次模函数最大化问题，提出了逼近算法，并在限制相对较小的情况下，得到了相对较好的逼近结果，并应用结果解决了更普遍的独立性约束下的最大化问题。

    Jul, 2015

  • 快速子模函数最大化

    本研究提出了一种基于新型搜索树数据结构的算法，可以高效地计算在线和离线子模函数最大值问题。

    May, 2023

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

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

    May, 2019

  • 基于拟阵约束的 k 次次模最大化的快速算法

    应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数，提出逼近算法来最大化满足单调和非单调 k - 次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。

    Jul, 2023

  • 子模量极大化的 FAST 算法

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

    Jul, 2019

  • 非子模目标强鲁棒性最大化

    研究了在最劣情况下，基于一个基数约束 k 最大化单调集合函数的删除问题，提出了一种新的算法 Oblivious-Greedy，并对于更广泛的非凸优化问题证明了首个常数因子逼近保证，通过提出新的度量参数，如逆曲率，证明了这些结果适用于线性区域，并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。

    Feb, 2018

  • 鲁棒子模最大化：一种非均匀划分方法

    本文研究了在确定性的 $ au$ 时，如何在满足固定大小约束 $k$ 的条件下最大化单调子模函数。提出了新的分区鲁棒性子模最大化算法，其构造具有指数增加大小的桶的分区，并在桶上应用标准子模优化子例程，证明了我们的算法对于更一般的 $ au = o（k）$ 具有相同的保证。在数据汇总和影响最大化方面，数值上验证了 PRo 的性能，并展示了对贪婪算法和 Orlin 等人的算法的优势。

    Jun, 2017

  • 具有近似最优的适应性和查询复杂度的子模最大化

    本文研究自适应子模型优化的适应性和查询复杂度，提出了适用于最大基数约束的单调子模型函数的分布式算法，并将其推广到子模型覆盖问题。

    Jul, 2018