BriefGPT.xyz
May, 2024
自适应次模覆盖问题的贪婪近似比的下界
Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
HTML
PDF
Blake Harris, Viswanath Nagarajan
TL;DR
贪婪算法的自适应子模块覆盖近似比率至少为1.3 *（1 + ln Q），这篇论文否定了Golovin-Krause在``自适应子模块性：主动学习和随机优化的新方法''中宣称相同算法具有（1 + ln Q）^2近似比率的先前结果。
Abstract
We show that the
greedy algorithm
for
adaptive-submodular cover
has
approximation ratio
at least 1.3*(1+ln Q). Moreover, the instance demo
→