or-Submodular Maximization Under a Matroid Constraint and a Knapsack Constraint

As a generalization of k-submodular function, or-submodular functions satisfy r-wise monotone, instead of pair-wise monotone. The problem of maximizing an or-submodular function under different constraints arises in many applications, and it is NP-hard. In this paper, we utilize a greedy algorithm to get a \(\frac{1}{r+1}\) -approximation solution for maximizing an or-submodular function under a matroid constraint. Moreover, for maximizing an or-submodular function with a knapsack constraint, we also design a \(\frac{1}{r+1}(1-e^{-(r+1)})\) -approximation algorithm.