本文研究了在确定性的 $ au$ 时,如何在满足固定大小约束 $k$ 的条件下最大化单调子模函数。提出了新的分区鲁棒性子模最大化算法,其构造具有指数增加大小的桶的分区,并在桶上应用标准子模优化子例程,证明了我们的算法对于更一般的 $ au = o(k)$ 具有相同的保证。在数据汇总和影响最大化方面,数值上验证了PRo的性能,并展示了对贪婪算法和Orlin等人的算法的优势。
Jun, 2017
研究了在最劣情况下,基于一个基数约束k最大化单调集合函数的删除问题,提出了一种新的算法Oblivious-Greedy,并对于更广泛的非凸优化问题证明了首个常数因子逼近保证,通过提出新的度量参数,如逆曲率,证明了这些结果适用于线性区域,并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。
Feb, 2018
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了5.83近似和O(nlogn)时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020
本文研究在传统的拟阵约束下,单调子模函数的删除鲁棒版本的最大化问题,提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法,在中心化、流式环境下均获得了好的结果。
Jan, 2022
该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题,在此问题中,目标是提取一个小型数据集的摘要,即使在对手删除一些元素后也包含高价值独立集,该研究提供了具有常数因子逼近比的近似算法,其中空间复杂度取决于拟阵的秩k和已删除元素的数量d。
Aug, 2022
本文研究了鲁棒优化在序列网络子模极大化问题中的应用,设计了一个鲁棒贪心算法并在实际应用中进行了实验,证明算法的有效性。
Dec, 2022
本文提出了单遍流式和在线算法的受约束k-次模最大化,其中包含基数和背包约束限制,该算法可以提供不错的近似解和高效的解决方案,并在广告分配等应用实例上得到了验证。
May, 2023
研究通过提出算法解决组合优化中的迷你最大化问题,并将其成功应用于机器学习领域,包括提问和对话状态检测等多个应用中的鲁棒解决方案。
非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近
Aug, 2023
提出了两个确定性近似算法来解决非单调k-次模极大化问题,其在查询复杂度仅为O(nk)的情况下提供了常数近似比率,比现有算法少使用了Omega(log n)数量的查询。
Sep, 2023