Maximization of nonsubmodular functions under multiple constraints with applications
Maximization of nonsubmodular functions under multiple constraints with applications
复制标题
应用程序多重约束下非子模函数的最大化
DOI：
10.1016/j.automatica.2023.111126
复制
发表时间：
2023
期刊：
影响因子：
6.4
通讯作者：
Gupta, Vijay
中科院分区：
文献类型：
--
作者：
Ye, Lintao;Liu, Zhi-Wei;Chi, Ming;Gupta, Vijay
考虑多约束条件下单调非减集函数的极大化问题，其中约束条件也是单调非减集函数。我们提出了两个贪婪算法来解决这个问题的可证明的近似保证。第一个算法利用一般问题实例的特殊类的结构来获得更好的时间复杂度。第二种算法适用于一般问题。我们的特点的近似保证的两个算法，利用子模比和曲率的概念引入集函数。然后，我们讨论了特定的应用程序的一般问题制定的问题，已被认为是在文献中。我们用数值例子验证了我们的理论结果。
We consider the problem of maximizing a monotone nondecreasing set function under multiple constraints, where the constraints are also characterized by monotone nondecreasing set functions. We propose two greedy algorithms to solve the problem with provable approximation guarantees. The first algorithm exploits the structure of a special class of the general problem instance to obtain a better time complexity. The second algorithm is suitable for the general problem. We characterize the approximation guarantees of the two algorithms, leveraging the notions of submodularity ratio and curvature introduced for set functions. We then discuss particular applications of the general problem formulation to problems that have been considered in the literature. We validate our theoretical results using numerical examples.