Paper Info
Title
Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint
Abstract
ABSTRACTMonotone submodular maximization with a knapsack constraint is NP-hard. Various approximation algorithms have been devised to address this optimization problem. In this paper, we revisit the widely known modified greedy algorithm. First, we show that this algorithm can achieve an approximation factor of 0.405, which significantly improves the known factors of 0.357 given by Wolsey and (1-1/e)/2-0.316 given by Khuller et al. More importantly, our analysis closes a gap in Khuller et al.'s proof for the extensively mentioned approximation factor of (1-1/√e)≈0.393 in the literature to clarify a long-standing misconception on this issue. Second, we enhance the modified greedy algorithm to derive a data-dependent upper bound on the optimum, which enables us to obtain a data-dependent ratio typically much higher than 0.405 between the solution value of the modified greedy algorithm and the optimum. It can also be used to significantly improve the efficiency of algorithms such as branch and bound.
Year
DOI
Venue
2021
10.1145/3410220.3453925
Measurement and Modeling of Computer Systems
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Jing Tang111.04
Xueyan Tang2155992.36
Andrew Lim38810.38
Kai Han426921.79
Chongshou Li5154.94
Junsong Yuan63703187.68