Search Results

Documents authored by Mendoza-Cadena, Mirabel

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.142
Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules

Authors: Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen, and Kevin Schewior

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system (E,ℐ), a schedule consists of an independent set I_t ∈ ℐ for every time step t ∈ ℕ, 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 ∈ 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 ℐ. Using the integrality of the matroid-intersection polytope, we prove that, when (E,ℐ) 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 ∈ E needs to occur in the schedule at least every a_e ∈ ℕ time steps, our results imply bounds on the density sufficient for schedulability.
Cite as

Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen, and Kevin Schewior. Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 142:1-142:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mendozacadena_et_al:LIPIcs.ICALP.2026.142,
  author =	{Mendoza-Cadena, Mirabel and Merino, Arturo and Nielsen, Mads Anker and Schewior, Kevin},
  title =	{{Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{142:1--142:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.142},
  URN =		{urn:nbn:de:0030-drops-265319},
  doi =		{10.4230/LIPIcs.ICALP.2026.142},
  annote =	{Keywords: Perpetual Scheduling, Matroids, Bamboo Garden Trimming, Pinwheel}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact