Non-Submodular Maximization Subject to a Knapsack Constraint on the Integer Lattice

The emergence of applications in machine learning, social networks, and sensor placement has naturally introduced challenges in maximizing submodular or non-submodular functions over integer lattices under knapsack constraints. While efficient algorithms exist for maximizing monotone non-negative submodular functions over both finite sets and integer lattices, these methods do not generalize straightforwardly to non-submodular objectives. To address this gap, we propose a two-phase greedy algorithm with a provable approximation ratio of Formula: see text, given that the objective function satisfies the Diminishing Return ratio (DR-ratio) Formula: see text and the generalized curvature Formula: see text. To our knowledge, this represents the first non-trivial approximation guarantee for such problem. Experimental evaluations demonstrate the algorithm’s practical effectiveness.