论文标题
分配和近似下函数的分布式最大化
Distributed Maximization of Submodular and Approximately Submodular Functions
论文作者
论文摘要
我们研究了最大化的子管函数的问题，但要受到基数约束，一组代理在连接的图上进行通信。我们提出了一种分布式的贪婪算法，该算法允许所有代理仅使用局部信息并与图中的邻居进行通信，从而将所有代理收敛到近乎最佳的解决方案。近距离解决方案将最佳解决方案（1-1/e）近似与全局最大化问题的近似相近似，并取决于算法中通信步骤的数量。然后，我们分析提出的算法的收敛保证。该分析揭示了通信步骤数量与算法的性能之间的权衡。最后，我们使用近似suploduline的概念将分析扩展到非模块化设置。
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.
