2020/11/30 by Rezazadeh, Navid, Kia, Solmaz S.
#Distributed #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Parallel #Systems and Control (eess.SY) #and Cluster Computing (cs.DC) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.2011.14499
Constrained submodular set function maximization problems often appear in multi-agent decision-making problems with a discrete feasible set. A prominent example is the problem of multi-agent mobile sensor placement over a discrete domain. However, submodular set function optimization problems are known to be NP-hard. In this paper, we consider a class of submodular optimization problems that consists of maximization of a monotone and submodular set function subject to a uniform matroid constraint over a group of networked agents that communicate over a connected undirected graph. Our objective is to obtain a distributed suboptimal polynomial-time algorithm that enables each agent to obtain its respective policy via local interactions with its neighboring agents. Our solution is a fully distributed gradient-based algorithm using the multilinear extension of the submodular set functions and exploiting a maximum consensus scheme. This algorithm results in a policy set that when the team objective function is evaluated at worst case the objective function value is in 1-1/e-O(1/T) of the optimal solution. An example demonstrates our results.