Title: Performance guarantees for greedy maximization of non-submodular set functions in systems and control.
Abstract: A key problem in emerging complex cyber-physical networks is the design of information and control topologies, including sensor and actuator selection and communication network design. These problems can be posed as combinatorial set function optimization problems to maximize a dynamic performance metric for the network. Some systems and control metrics feature a property called submodularity, which allows simple greedy algorithms to obtain provably near-optimal topology designs. However, many important metrics lack submodularity and therefore lack any guarantees from the existing theory. Here we show that performance guarantees can be obtained for greedy maximization of certain non-submodular functions of the controllability and observability Gramians. We derive from bounds on two key quantities: the submodularity ratio, which quantifies how far a set function is from being submodular, and the generalized curvature, which quantifies how far a set function is from being modular. Numerical experiments illustrate the results.
Publication Year: 2017
Publication Date: 2017-12-12
Language: en
Type: article
Access and Citation
Cited By Count: 12
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot