Latest News

Distributed Strategy Selection: A Submodular Set Function Maximization Approach. (arXiv:2107.14371v1 [math.OC])

[Submitted on 29 Jul 2021]

Download PDF

Abstract: 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. Submodular set function optimization problems, however, are known to be
NP-hard. This paper considers a class of submodular optimization problems that
consist 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. We work in the value oracle model where the
only access of the agents to the utility function is through a black box that
returns the utility function value. We propose a distributed suboptimal
polynomial-time algorithm that enables each agent to obtain its respective
strategy via local interactions with its neighboring agents. Our solution is a
fully distributed gradient-based algorithm using the submodular set functions’
multilinear extension followed by a distributed stochastic Pipage rounding
procedure. This algorithm results in a strategy set that when the team utility
function is evaluated at worst case, the utility function value is in
1/c(1-e^(-c)-O(1/T)) of the optimal solution with c to be the curvature of the
submodular function. An example demonstrates our results.

Submission history

From: Navid Rezazadeh [view email]

Thu, 29 Jul 2021 23:36:52 UTC (261 KB)

Read More

Show More

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button

Adblock Detected

Please consider supporting us by disabling your ad blocker