Distributed Submodular Maximization with Parallel Execution
- Creators
- Sun, Haoyuan
- Grimsman, David
- Marden, Jason R.
Abstract
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.
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.Attached Files
Submitted - 2003.04364.pdf
Files
Name | Size | Download all |
---|---|---|
md5:5b2a20ed4b90cdbc5f27577427399de1
|
547.9 kB | Preview Download |
Additional details
- Eprint ID
- 104666
- Resolver ID
- CaltechAUTHORS:20200730-143943179
- ECCS-1638214
- NSF
- N00014-17-1-2060
- Office of Naval Research (ONR)
- Created
-
2020-07-31Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field