A Refined Analysis of Submodular Greedy

02/25/2021

∙

by   Ariel Kulik, et al.

∙

0

∙

share

Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy heuristic which enables us to: (1) reduce the enumeration in the tight (1-e^-1)-approximation of [Sviridenko 04] from subsets of size three to two; (2) present an improved upper bound of 0.42945 for the classic algorithm which returns the better between a single element and the output of the greedy heuristic.