A Caltech Library Service

Distributed Submodular Maximization with Parallel Execution

Sun, Haoyuan and Grimsman, David and Marden, Jason R. (2020) Distributed Submodular Maximization with Parallel Execution. In: 2020 American Control Conference (ACC). IEEE , Piscataway, NJ, pp. 1477-1482. ISBN 9781538682661.

[img] PDF - Submitted Version
Creative Commons Attribution Non-commercial Share Alike.


Use this Persistent URL to link to this item:


The submodular maximization problem is widely applicable in many engineering problems where objectives exhibit diminishing returns. While this problem is known to be NP-hard for certain subclasses of objective functions, there is a greedy algorithm which guarantees approximation at least 1/2 of the optimal solution. This greedy algorithm can be implemented with a set of agents, each making a decision sequentially based on the choices of all prior agents. In this paper, we consider a generalization of the greedy algorithm in which agents can make decisions in parallel, rather than strictly in sequence. In particular, we are interested in partitioning the agents, where a set of agents in the partition all make a decision simultaneously based on the choices of prior agents, so that the algorithm terminates in limited iterations. We provide bounds on the performance of this parallelized version of the greedy algorithm and show that dividing the agents evenly among the sets in the partition yields an optimal structure. It is shown that such optimal structures holds even under very relaxed information constraints. We additionally show that this optimal structure is still near-optimal, even when additional information (i.e., total curvature) is known about the objective function.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Grimsman, David0000-0003-3350-382X
Marden, Jason R.0000-0003-3260-8574
Additional Information:© 2020 AACC. This research was supported by NSF Grant #ECCS-1638214 and U.S. Office of Naval Research (ONR) grant #N00014-17-1-2060.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-17-1-2060
Record Number:CaltechAUTHORS:20200730-143943179
Persistent URL:
Official Citation:H. Sun, D. Grimsman and J. R. Marden, "Distributed Submodular Maximization with Parallel Execution," 2020 American Control Conference (ACC), Denver, CO, USA, 2020, pp. 1477-1482, doi: 10.23919/ACC45564.2020.9147476
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104666
Deposited By: George Porter
Deposited On:31 Jul 2020 14:28
Last Modified:16 Nov 2021 18:33

Repository Staff Only: item control page