Stochastic greedy algorithms for maximizing constrained submodular plus supermodular functions

The problem of maximizing the sum of a constrained submodular and a supermodular function has many applications such as social networks, machine learning, and artificial intelligence. In this article, we study the monotone submodular + supermodular maximization problem under a cardinality constraint and a p-system constraint, respectively. For each problem, we provide a stochastic algorithm and prove the approximation ratio of each algorithm theoretically. Since the algorithm of the latter problem can also solve the former problem, we do some numerical experiments of the two algorithms to compare the time as well as the quality of the two algorithms in solving the former problem.

Automated summary

This article studies the problem of maximizing the sum of a constrained submodular and a supermodular function under a cardinality constraint and a p-system constraint. It provides stochastic algorithms for each problem and theoretically proves the approximation ratio of each algorithm. Numerical experiments are conducted to compare the time and quality of the two algorithms in solving the former problem.