Journal
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
Volume 35, Issue 17, Pages -Publisher
WILEY
DOI: 10.1002/cpe.6575
Keywords
approximation algorithm; constrained; stochastic greedy; submodular plus supermodular maximization
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available