Budget-Smoothed Analysis for Submodular Maximization
Budget-Smoothed Analysis for Submodular Maximization
复制标题
DOI：
10.4230/lipics.itcs.2022.113
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
A. Rubinstein;Junyao Zhao
中科院分区：
文献类型：
--
作者：
A. Rubinstein;Junyao Zhao
在基数约束下，单调子模函数极大化问题的贪婪算法保证在1 -1/e因子内逼近最优解。虽然众所周知，这种保证在最坏的情况下基本上是严格的-对于贪婪算法和实际上任何有效的算法，实验表明贪婪算法在实践中表现得更好。我们观察到，对于实践中的许多应用，预算的经验分布（即，基数约束）在很宽的范围内得到支持，而且，所有现有的硬度导致在预算的大扰动下理论破裂。为了从算法和硬度的角度来理解预算的影响，我们引入了预算平滑分析的新概念。我们证明了贪婪是最优的每一个预算分布，我们给出了最坏情况下的子模函数的一个特征。基于这些结果，我们表明，在算法方面，根据现实的预算分布，贪婪和相关算法享有可证明更好的近似保证，即使是最坏情况下的功能，并在硬度方面，存在硬功能，是相当强大的所有预算分布。
The greedy algorithm for monotone submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a $1-1/e$ factor. Although it is well known that this guarantee is essentially tight in the worst case -- for greedy and in fact any efficient algorithm, experiments show that greedy performs better in practice. We observe that for many applications in practice, the empirical distribution of the budgets (i.e., cardinality constraints) is supported on a wide range, and moreover, all the existing hardness results in theory break under a large perturbation of the budget. To understand the effect of the budget from both algorithmic and hardness perspectives, we introduce a new notion of budget smoothed analysis. We prove that greedy is optimal for every budget distribution, and we give a characterization for the worst-case submodular functions. Based on these results, we show that on the algorithmic side, under realistic budget distributions, greedy and related algorithms enjoy provably better approximation guarantees, that hold even for worst-case functions, and on the hardness side, there exist hard functions that are fairly robust to all the budget distributions.