Maximizing a monotone non-submodular function under a knapsack constraint

Submodular optimization has been well studied in combinatorial optimization. However, there are few works considering about non-submodular optimization problems which also have many applications, such as experimental design, some optimization problems in social networks, etc. In this paper, we consider the maximization of non-submodular function under a knapsack constraint, and explore the performance of the greedy algorithm, which is characterized by the submodularity ratio $$\beta $$ β and curvature $$\alpha $$ α . In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of $$ (1-e^{-\alpha \beta })/{\alpha }$$ ( 1 - e - α β ) / α for the above problem. To our knowledge, it is the first tight constant factor for this problem. We further utilize illustrative examples to demonstrate the performance of our algorithm.