Distributed Maximization of Submodular and Approximately Submodular Functions
Distributed Maximization of Submodular and Approximately Submodular Functions
复制标题
DOI：
10.1109/cdc42340.2020.9304492
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Lintao Ye;S. Sundaram
中科院分区：
文献类型：
--
作者：
Lintao Ye;S. Sundaram
我们研究的问题，最大化的子模块功能，受基数约束，与一组代理在一个连接的图进行通信。我们提出了一个分布式的贪婪算法，允许所有的代理收敛到一个接近最优的解决方案的全局最大化问题，只使用本地信息和通信与邻居的图形。近似最优解接近全局最大化问题的最优解的（1−1/e）近似值，其加性因子取决于算法中的通信步骤数。然后，我们分析所提出的算法的收敛保证。该分析揭示了通信步骤的数量和算法的性能之间的权衡。最后，我们扩展我们的分析nonsubmodular设置，使用近似次模块化的概念。
We study the problem of maximizing a submodular function, subject to a cardinality constraint, with a set of agents communicating over a connected graph. We propose a distributed greedy algorithm that allows all the agents to converge to a near-optimal solution to the global maximization problem using only local information and communication with neighbors in the graph. The near-optimal solution approaches the (1−1/e) approximation of the optimal solution to the global maximization problem with an additive factor that depends on the number of communication steps in the algorithm. We then analyze convergence guarantees of the proposed algorithm. This analysis reveals a tradeoff between the number of communication steps and the performance of the algorithm. Finally, we extend our analysis to nonsubmodular settings, using the notion of approximate submodularity.