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.
翻译:单调子模块功能最大化的贪婪算法受到基本限制,可以保证将最佳解决办法接近于1-1/e美元因素。虽然众所周知,这种保证在最坏的情况下基本上很紧 -- -- 贪婪和事实上是有效的算法,但实验表明贪婪在实践中表现更好。我们观察到,对于许多应用,预算的经验分配(即最基本限制)在广泛的范围内得到支持,此外,理论在预算的大扰动下打破了所有现有的硬性结果。为了从算法和硬性角度理解预算的影响,我们引入了预算平稳分析的新概念。我们证明贪婪是每个预算分配的最佳办法,我们给最坏的子模块功能作了定性。基于这些结果,我们表明,在算法方面,根据现实的预算分配,贪婪和相关算法享有可被证实的更好近似保证,即使最坏的功能也存在,在硬性方面,存在对所有预算分配相当稳健的硬功能。