Nearly Linear Time Deterministic Algorithms for Submodular Maximization Under Knapsack Constraint and Beyond

Wenxin Li

In this work, we study the classic submodular maximization problem under knapsack constraints and beyond. We first present an $(7/16-\epsilon )$-approximate algorithm for single…