Maximizing a non-decreasing non-submodular function subject to various types of constraints

In this paper, we firstly study the problem of maximizing a gamma-weakly DR-submodular function under a general matroid constraint. We present a local search algorithm, which is guided by a tailored potential function, for solving this problem. We prove that our algorithm produces a (1 - e(-gamma) - epsilon)-approximate solution. To the best of our knowledge, it's the first algorithm achieving the tight approximation guarantee for such maximization problem. In addition, we study the maximization of the sum of submodular and supermodular functions. We show that this problem can be reduced to the maximization of submodular and linear sums. Based on this reduction, we derive new and improved approximation bounds for the problem under various types of constraints.