Partial Monotonicity for Submodular Maximization with a Knapsack Constraint

Submodular maximization has become increasingly important in the fields of machine learning and data mining. For general submodular maximization without monotonicity, many previous analyses provide poor approximation guarantees, especially for submodular functions that are approximately monotone. To address this issue, the research community has proposed a continuous metric called the monotonicity ratio for submodular functions. The monotonicity ratio has been studied for submodular maximization under no constraint, cardinality constraint, and matroid constraint. However, the implications of using the monotonicity ratio for submodular maximization with a knapsack constraint remain unclear. Although a knapsack constraint can be regarded as a continuous extension of the cardinality constraint with non-uniform costs, the gap in analysis between these two constraints is substantial. In this paper, we analytically show that many previously proposed algorithms for monotone submodular maximization with a knapsack constraint can achieve improved approximation guarantees under partial monotonicity with a simple modification: enforcing positive marginal gain. In addition to the theoretical analysis, we have evaluated our proposed algorithms for two machine learning applications of movie recommendation and influence-and-exploit marketing, showing that our algorithms could achieve better performance to state-of-the-art algorithms under partial monotonicity.