IEEE Transactions on Control of Network Systems · 2015 · 487 citations · 44 references
Natural SciencesMathematicsSystems EngineeringComplex SystemsDynamical SystemsOptimizationApproximation AlgorithmsCombinatorial OptimizationControl SystemsControl TheoryNetwork OptimizationNetwork TheoryActuator PlacementComplex NetworksControllabilityGreedy HeuristicsObservabilityOptimization Of Complex SystemsSubmodular MaximizationSubmodular Optimization
Controllability and observability are fundamental structural properties of dynamical systems, and recent interest in large complex networks has highlighted the sensor and actuator placement problem, yet the combinatorial optimization structure remains poorly understood. The paper demonstrates that key controllability and observability Gramian‑based metrics possess structural properties enabling efficient global optimization or greedy approximation guarantees. The authors show that the mapping from placements to scalar Gramian functions is modular or submodular. The approach is validated on synthetic systems and on power electronic actuator placement in a European power grid model.
Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this paper, we show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on randomly generated systems and on a problem of power electronic actuator placement in a model of the European power grid.
44
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Controllability of complex networks
Yang‐Yu Liu, Jean-Jacques Slotine, Albert-Ĺaszló Barabási · Nature · 2011 · 3.3K citations
A threshold of ln <i>n</i> for approximating set cover
Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text