View publication
| Title | Perpetual Scheduling: Existence and Computation of Low-Height Schedules |
| Authors | Mirabel Mendoza-Cadena, Arturo Merino, Kevin Schewior, Mads Anker Nielsen |
| Publication date | 2026 |
| Abstract | This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system (E,S), a schedule consists of an independent set I_t \in S for every time step t \in N, 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 e \in E and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. We assume that g is normalized so that it is a convex combination of the incidence vectors of S. Using the integrality of the matroid-intersection polytope, we prove that, when (E,S) is a matroid, it is possible to guarantee a maximum height of at most 2, which is optimal. We complement this existential result with efficient algorithms for specific matroid classes, achieving a maximum height of 2 for uniform and partition matroids, and 4 for graphic and laminar matroids. In contrast, we show that for general independence systems, the optimal guaranteed height is Theta(log |E|) and can be achieved by an efficient algorithm. For combinatorial pinwheel scheduling, where each element e \in E needs to occur in the schedule at least every a_e \in N time steps, our results imply bounds on the density sufficient for schedulability. |
| Pages | 142:1-142:23 |
| Conference name | International Colloquium on Automata, Languages, and Programming |