Impact of Information in Greedy Submodular Maximization - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Impact of Information in Greedy Submodular Maximization

(1) , (2, 3) , (1) , (1)


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.
Fichier non déposé

Dates et versions

hal-02287622 , version 1 (13-09-2019)


  • 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⟩
15 Consultations
0 Téléchargements


Gmail Facebook Twitter LinkedIn More