k 秘书问题的新结果
本文提出了一种称为 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) 逼近,这大大提高了以前已知的逼近因子。
Sep, 2018
本文介绍的是先知秘书问题,研究从已知的概率分布中随机选取样本的决策过程,在该决策过程中,算法必须在样本到来时立即选择一个样本,目标是使其相对于分布最大值的期望最大化。作者提出了一种新算法,该算法击败了 1-1/e 的边界,取得了 1-1/e+1/400 的最优值。
Nov, 2017
本文介绍一种自然结合了 prophet inequality 和 secretary problem 的问题 ——Prophet Secretary,对于一些类似拍卖的场景,研究优化一个不确定情况下的分配过程中停止规则空间内的目标函数。发现使用 $n$ 个独立的非自适应阈值可以得到比 0.5 更高的竞争比率,上限约为 $(1-1/e)$,但无在线算法可以达到更好的竞争比率。当随机选择代理(客户)的顺序时,我们将单个项目的顺序定价机制的渐近近似保证从 0.5 提高到了 $(1-1/e)$。
Jul, 2015
在给定的有向图中选择一个大小为 k 的代理人子集,将入度之和最大化,并设计不需要付款的机制以满足策略无关性和近似最优性约束。具有近似比例边界的策略无关机制的近似比例上限为四对于任何 k 值,并随着 k 的增加逼近一。
Oct, 2009
本研究中,我们研究了在随机顺序模型下,针对背包问题和广义分配问题的在线算法,提出了一种基于两个优化算法的新型算法,竞争比最高达到 1/6.65 和 1/6.99。
Dec, 2020
本文研究基于在线变体的子模函数最大化问题,探讨了两种特殊情况并得出了竞争比的上下界。具体而言,设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。
Jan, 2015