[Scheduling seminar] Kevin Schewior (University of Cologne) | Combinatorial Perpetual Scheduling

Описание: Keywords: Perpetual Scheduling, Matroids, Bamboo Garden Trimming, Pinwheel

In this talk, I am going to give an overview of recent developments in perpetual scheduling, with a focus on combinatorial versions. Here, given a set system I on a ground set E, a (perpetual) schedule consists of an independent set from I for every discrete time step, with the objective of fulfilling frequency requirements on the occurrence of elements in E. We focus specifically on combinatorial bamboo garden trimming, where elements accumulate height at growth rates g(e) for element e and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. As a normalization, we assume that the vector of growth rates is given as a convex combination of incidence vectors from I. We prove that, when the set system is a matroid, it is possible to guarantee a maximum height of at most 2, which is optimal. For general set systems, one can only guarantee a height that is logarithmic in the cardinality of E. The talk is partially based on joint work with Mirabel Mendoza-Cadena, Arturo Merino, and Mads Anker Nielsen.


Organized by Zdenek Hanzalek (CTU in Prague), Michael Pinedo (New York University), and Guohua Wan (Shanghai Jiao Tong).

Seminar's webpage: https://schedulingseminar.com/