Paper Detail
Sotiris Kanellopoulos
In perpetual scheduling theory, the Pinwheel Covering problem asks, given $n$ frequencies $f_i$, whether there exists an infinite schedule such that every $f_i$ consecutive entries contain at most one occurrence of $i\in [n]$. This models $n$ agents taking turns at executing a job, with a recovery period before working again. Pinwheel Covering is, in a sense, the dual of Pinwheel Packing (also known as Pinwheel Scheduling), which similarly asks for at least one occurrence of $i$ in every $f_i$ consecutive entries. The complexity of both problems is a major open question: both are known to be in PSPACE, but PSPACE-hardness remains unknown. Recently, a finite version of Pinwheel Packing requiring only $k$ occurrences of $i\in [n]$ was introduced by [Kanellopoulos et al., SODA 2026] and proven to be strongly NP-complete. In this work we introduce $k$-Visits Covering, the analogous finite version of Pinwheel Covering, establishing strong NP-completeness even for $k=2$. As a corollary, we obtain that a generalization of Pinwheel Covering with varying frequencies is strongly NP-hard. To the best of our knowledge, this is the first strong NP-hardness result in the covering setting. We complement these results with a linear-time algorithm for $2$-Visits Covering with two distinct frequencies and a randomized polynomial-time algorithm when the number of distinct frequencies is constant. Lastly, we study the density thresholds of $k$-Visits Covering and prove that no non-trivial density bounds exist, contrasting the finite packing version.
No structured notes yet. Add `summary_sections`, `why_relevant`, `claim_impact`, or `next_action` in `papers.jsonl` to enrich this view.
No ranking explanation is available yet.
No tags.
@article{kanellopoulos2026finite,
title = {Finite Pinwheel Covering},
author = {Sotiris Kanellopoulos},
year = {2026},
abstract = {In perpetual scheduling theory, the Pinwheel Covering problem asks, given \$n\$ frequencies \$f\_i\$, whether there exists an infinite schedule such that every \$f\_i\$ consecutive entries contain at most one occurrence of \$i\textbackslash{}in [n]\$. This models \$n\$ agents taking turns at executing a job, with a recovery period before working again. Pinwheel Covering is, in a sense, the dual of Pinwheel Packing (also known as Pinwheel Scheduling), which similarly asks for at least one occurrence of \$i\$ in every \$f\_i\$ c},
url = {https://arxiv.org/abs/2607.28574},
keywords = {cs.DS},
eprint = {2607.28574},
archiveprefix = {arXiv},
}
{}