Stochastic greedy algorithms for maximizing constrained submodular + supermodular functions
Stochastic greedy algorithms for maximizing constrained submodular + supermodular functions
复制标题
DOI：
10.1002/cpe.6575
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
S. Ji;Dachuan Xu;Min Li;Yishui Wang;Dongmei Zhang
中科院分区：
文献类型：
--
作者：
S. Ji;Dachuan Xu;Min Li;Yishui Wang;Dongmei Zhang
最大化受约束子模函数和超模函数之和的问题具有许多应用，例如社交网络、机器学习和人工智能。在本文中，我们分别研究基数约束和 p 系统约束下的单调子模 + 超模最大化问题。对于每个问题，我们提供了一个随机算法，并从理论上证明了每个算法的逼近率。由于后一问题的算法也可以解决前一问题，因此我们对两种算法进行了一些数值实验，以比较两种算法解决前一问题的时间和质量。
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.