TY - JOUR
T1 - A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
AU - Welikala, Shirantha
AU - Cassandras, Christos G.
AU - Lin, Hai
AU - Antsaklis, Panos J.
N1 - Publisher Copyright:
© 2022 Elsevier Ltd
PY - 2022/10
Y1 - 2022/10
N2 - Several important problems in multi-agent systems, machine learning, data mining, scheduling and others, may be formulated as set function maximization problems subject to cardinality constraints. In such problems, the set (objective) functions of interest often have monotonicity and submodularity properties. Hence, the class of monotone submodular set function maximization problems has been widely studied in the literature. Owing to its challenging nature, almost all existing solutions for this class of problems are based on greedy algorithms. A seminal work on this topic has exploited the submodularity property to prove a (1-1/e) performance bound for such greedy solutions. More recent literature on this topic has been focused on exploiting different curvature properties to establish improved (tighter) performance bounds. However, such improvements come at the cost of enforcing additional assumptions and increasing computational complexity while facing significant inherent limitations. In this paper, first, a brief review of existing performance bounds is provided. Then, a new performance bound that does not require any additional assumptions and is both practical and computationally inexpensive is proposed. In particular, this new performance bound is established based on a series of upper bounds derived for the objective function that can be computed in parallel with the execution of the greedy algorithm. Finally, to highlight the effectiveness of the proposed performance bound, extensive numerical results obtained from a well-known class of multi-agent coverage problems are provided.
AB - Several important problems in multi-agent systems, machine learning, data mining, scheduling and others, may be formulated as set function maximization problems subject to cardinality constraints. In such problems, the set (objective) functions of interest often have monotonicity and submodularity properties. Hence, the class of monotone submodular set function maximization problems has been widely studied in the literature. Owing to its challenging nature, almost all existing solutions for this class of problems are based on greedy algorithms. A seminal work on this topic has exploited the submodularity property to prove a (1-1/e) performance bound for such greedy solutions. More recent literature on this topic has been focused on exploiting different curvature properties to establish improved (tighter) performance bounds. However, such improvements come at the cost of enforcing additional assumptions and increasing computational complexity while facing significant inherent limitations. In this paper, first, a brief review of existing performance bounds is provided. Then, a new performance bound that does not require any additional assumptions and is both practical and computationally inexpensive is proposed. In particular, this new performance bound is established based on a series of upper bounds derived for the objective function that can be computed in parallel with the execution of the greedy algorithm. Finally, to highlight the effectiveness of the proposed performance bound, extensive numerical results obtained from a well-known class of multi-agent coverage problems are provided.
KW - Control of networks
KW - Cooperative control
KW - Multi-agent systems
KW - Optimization
KW - Parametric control
KW - Persistent monitoring
UR - http://www.scopus.com/inward/record.url?scp=85134801499&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134801499&partnerID=8YFLogxK
U2 - 10.1016/j.automatica.2022.110493
DO - 10.1016/j.automatica.2022.110493
M3 - Article
AN - SCOPUS:85134801499
SN - 0005-1098
VL - 144
JO - Automatica
JF - Automatica
M1 - 110493
ER -