Zhenwei Liu

Zhenwei Liu, Ali Saberi, Anton A. Stoorvogel et al.

This paper studies delayed synchronization of continuous-time multi-agent systems (MAS) in the presence of unknown nonuniform communication delays. A delay-free transformation is developed based on a communication network which is a directed spanning tree, which can transform the original MAS to a new one without delays. By using this transformation, we design a static protocol for full-state coupling and a dynamic protocol for delayed state synchronization for homogeneous MAS via full- and partial-state coupling. Meanwhile, the delayed output synchronization is also studied for heterogeneous MAS, which is achieved by using a low-gain and output regulation based dynamic protocol design via the delay-free transformation.

Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr et al.

Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle modelling an unknown, potentially different matroid. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty matroids, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.