Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

Zihui Liu, Zhijie Zhang

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motiv…