Skip to Main content Skip to Navigation
Conference papers

Impact of Information in Greedy Submodular Maximization

Abstract : The maximization of submodular functions is a well-studied topic due to its application in many common engineering problems. Because this problem has been shown to be NP-Hard for certain subclasses of functions, much work has been done to develop efficient algorithms to approximate an optimal solution. Among these is a simple greedy algorithm, which has been shown to guarantee a solution within 1/2 the optimal. However, when this algorithm is implemented in a distributed way, it requires all agents to share information with one another - a costly constraint for some applications. This work explores how the degradation of information sharing among the agents affects the performance of the distributed greedy algorithm. For any underlying communication graph structure, we show results for how well the distributed greedy algorithm can perform. In addition, for applications where the number of agents and number of communication links is fixed, we identify near-optimal graph structures with the highest performance guarantees. This result can inform system designers as to the most impactful places to insert communication links.
Document type :
Conference papers
Complete list of metadatas
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 5:09:30 PM
Last modification on : Friday, July 31, 2020 - 11:28:08 AM


  • HAL Id : hal-02287622, version 1


David Grimsman, Mohammed Shabbir Ali, Joao P. Hespanha, Jason R. Marden. Impact of Information in Greedy Submodular Maximization. IEEE Conference on Decision and Control (CDC), Dec 2017, Melbourne, Australia. pp.1-7. ⟨hal-02287622⟩



Record views