Kevin Schewior

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen et al.

We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right. Each packet that is forwarded arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the difference between its release time and the time of its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al.~in 2014. They propose a collection of natural algorithms and prove for one, and claim for others, that none of them are $O(1)$-competitive. It was posed as an open problem whether such an algorithm exists. We make the first progress on answering this question. We consider the special case where each packet needs to be forwarded by exactly one or two routers. We show that a greedy algorithm, which was not previously considered for this problem, achieves a competitive ratio of exactly $2-2^{1-k}$, where $k$ is the number of active routers in the network. We also give a general lower bound of $4/3$, even for randomized algorithms.

Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen et al.

This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system $(E,\mathcal{I})$, a schedule consists of an independent set $I_t \in \mathcal{I}$ for every time step $t \in \mathbb{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 $\mathcal{I}$. Using the integrality of the matroid-intersection polytope, we prove that, when $(E,\mathcal{I})$ 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 $Θ(\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 \mathbb{N}$ time steps, our results imply bounds on the density sufficient for schedulability.