Scaling Submodular Optimization Approaches for Control Applications in
  Networked Systems
  Often times, in many design problems, there is a need to select a small set
of informative or representative elements from a large ground set of entities
in an optimal fashion. Submodular optimization that provides for a formal way
to solve such problems, has recently received significant attention from the
controls community where such subset selection problems are abound. However,
scaling these approaches to large systems can be challenging because of the
high computational complexity of the overall flow, in-part due to the
high-complexity compute-oracles used to determine the objective function
values. In this work, we explore a well-known paradigm, namely leader-selection
in a multi-agent networked environment to illustrate strategies for scalable
submodular optimization. We study the performance of the state-of-the-art
stochastic and distributed greedy algorithms as well as explore techniques that
accelerate the computation oracles within the optimization loop. We finally
present results combining accelerated greedy algorithms with accelerated
computation oracles and demonstrate significant speedups with little loss of
optimality when compared to the baseline ordinary greedy algorithm.
