Distributed strategy selection: a submodular set function maximization approach
From MaRDI portal
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.
Recommendations
- Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
- A mobile multi-agent sensing problem with submodular functions under a partition matroid
- Multi-agent submodular optimization
- Distributed submodular maximization
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
Cites work
- scientific article; zbMATH DE number 5888315 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A sub-modular receding horizon solution for mobile multi-agent persistent monitoring
- A threshold of ln n for approximating set cover
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Distributed Submodular Maximization With Limited Information
- On Submodularity and Controllability in Complex Dynamical Networks
- Optimal approximation for the submodular welfare problem in the value oracle model
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Stochastic conditional gradient methods: from convex minimization to submodular maximization
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems
- Submodularity of Storage Placement Optimization in Power Networks
- Tractability. Practical approaches to hard problems
Cited in
(6)- Multi-agent submodular optimization
- Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
- Utility Design for Distributed Resource Allocation—Part II: Applications to Submodular, Covering, and Supermodular Problems
- An exact solution approach for the mobile multi‐agent sensing problem
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
- A mobile multi-agent sensing problem with submodular functions under a partition matroid
This page was built for publication: Distributed strategy selection: a submodular set function maximization approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6110260)
