Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis, Thanos Tolias · 2026
Read Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants by Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis, Thanos Tolias (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16030.txt.
Introduction
Kanellopoulos and three colleagues study finite k-Visits Pinwheel Scheduling, asking whether length k times n schedules can run each task k times without a deadline expiring between visits. They prove 2-Visits is strongly NP-complete even at maximum multiplicity 2, settling an open question. They also prove 2-Visits lies in RP for constant distinct deadlines, advancing another open question. Results generalize to a mixed version, though 3-Visits transfer looks unlikely. They bound thresholds, with a lower bound above nine tenths for 2-Visits and a k-Visits threshold approaching five sixths.
Catalog record
| CREATOR | Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis, Thanos Tolias |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100511 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis, Thanos Tolias Abstract The k k - Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026 [ 28 ] ]. Given the deadlines of n n tasks, the problem asks whether there exists a schedule of length k n kn executing each task exactly k k times, with no deadline expiring between consecutive visits (executions) of each task. In this work we prove that 2 2 - Visits is strongly NP-complete even when the maximum multiplicity of the input is equal to 2 2 , settling an open question from [ 28 ] and contrasting the tractability of 2 2 - Visits for simple sets. On the other hand, we prove that 2 2 - Visits is in RP \mathrm{RP} when the number of distinct deadlines is constant, thus making progress on another open question regarding the parameterization of 2 2 - Visits by the number of numbers. We then generalize all existing positive results for 2 2 - Visits to a version of the problem where some tasks must be visited once and some other tasks twice, while providing evidence that some of these results are unlikely to transfer to 3 3 - Visits . Lastly, we establish bounds for the density thresholds of k k - Visits , analogous to the ( 5 / 6 ) (5/6) -threshold of Pinwheel Scheduling [Kawamura, STOC 2024 [ 30 ] ]; in particular, we show a 2 − 1 / 2 ≈ 0.9142 \sqrt{2}-1/2\approx 0.9142 lower bound for the density threshold of 2 2 - Visits and prove that the density threshold of k k -Visits approaches 5 / 6 ≈ 0.8333 5/6\approx 0.8333 for k → ∞ k\to\infty . 1 Introduction Pinwheel Scheduling is a fundamental problem in scheduling theory, introduced by Holte, Mok, Rosier, Tulchinsky and Varvel [ 23 ] in 1989. Given the deadlines of n tasks, the problem asks whether it is possible to perpetually execute one task at a time, in a way such that no deadline expires between consecutive executions of the same task. Since its introduction, this problem has been extensively studied; for instance, [ 24 ] and [ 33 ] study the problem for constant amounts of distinct deadlines, [ 26 ] studies its complexity and [ 17 ] introduces an optimization version known as Bamboo Garden Trimming . Pinwheel Scheduling has received significant attention in recent years, in particular after Kawamura’s breakthrough paper [ 30 ] in STOC 2024, in which a computer-assisted proof of the density threshold conjecture (i.e., that every Pinwheel Scheduling instance with sum of inverse deadlines at most 5/6 is a yes-instance) was given. This resolved a question that had remained open for over three decades [ 7 ] despite a substantial line of work in that direction [ 2 , 6 , 15 , 18 ] . Arguably the most important open question regarding Pinwheel Scheduling is its complexity: it is known that the problem is in PSPACE ever since its introduction [ 23 ] , but it remains open whether it is PSPACE-complete [ 5 ] . In fact, even (strong) NP-hardness and membership in NP are both open questions for this problem. Despite some progress for variants and special cases (e.g., membership in NP for dense instances [ 23 ] , NP-hardness for a compact input [ 2 ] , PSPACE-completeness of a weighted generalization [ 21 ] ), all the aforementioned questions still remain open. Regardless, Pinwheel Scheduling has been used to classify the complexity of other problems, in particular inventory routing problems [ 1 ] , adding further intrigue to these open questions. In a SODA 2026 paper, Kanellopoulos, Pergaminelis, Kokkou, Markou and Pagourtzis [ 28 ] introduced the k -Visits problem as a finite version of Pinwheel Scheduling and proved that it is strongly NP-complete for k=2 , contrasting the current state of the infinite version, which is not even known to be weakly NP-hard. As a corollary, Pinwheel Scheduling becomes strongly NP-hard if each task’s deadline is allowed to change once after a given amount of executions. This seems like substantial progress towards settling the complexity of Pinwheel Scheduling , especially when one considers that PSPACE-completeness proofs for periodic problems often rely on the NP-hardness of finite versions (see e.g., [ 34 , 38 ] ). Moreover, since the existence of an infinite schedule is equivalent to the existence of an infinite schedule with a finite period [ 23 ] , it might be possible to transfer some NP-hardness result from k -Visits to Pinwheel Scheduling , which would by itself resolve an open question. Even disregarding the potential of answering open questions of the infinite version, k -Visits seems like an interesting problem in its own merit: it may be more practical than Pinwheel Scheduling in applications that require finite repetitions, and it may be tractable in cases in which Pinwheel Scheduling is not. With the aforementioned motivations in mind, we build upon the work of [ 28 ] , establishing stronger hardness results and algorithms for 2 -Visits , as well as bounds for the density thresholds of k -Visits . See Section 1.2 for a comprehensive overview of our results and their merits. 1.1 Related Work The k -Visits problem was introduced by Kanellopoulos et al. [ 28 ] in SODA 2026 as a finite version of Pinwheel Scheduling . Interest in Pinwheel Scheduling and its variants has been reignited in recent years after Gasieniec, Smith and Wild [ 18 ] made progress towards the density threshold conjecture, and even more so after Kawamura [ 30 ] definitively proved the conjecture. This conjecture was stated by Chan and Chin [ 7 ] and had remained open for over three decades. Kanellopoulos et al. [ 28 ] prove that 2 -Visits is strongly NP-complete through a chain of reductions starting from Restricted Numerical 3 -Dimensional Matching ( RN3DM ) [ 40 ] . On the other hand, it can be solved in linear time when the input is a simple set or when the input consists of at most two distinct numbers. This leads to two natural open questions stated in [ 28 ] : whether 2 -Visits can be parameterized by the maximum multiplicity or by the number of numbers . A natural way to tackle the latter would be to try a reduction to Integer Linear Programming , which is a standard method for parameterizing numerical matching variants by the number of numbers (see the paper by Fellows, Gaspers and Rosamond [ 14 ] for more details). However, this method is insufficient for 2 -Visits , because its corresponding numerical matching variant ( Position Matching - Def. 7 ) contains two simple sets by definition, and the parameterization proposed by [ 14 ] for numerical matching variants uses the combined number of numbers of all input sets as parameter (which is \mathcal{O}(n) for Position Matching ). Regarding density thresholds for k -Visits , the (5/6) -threshold of Pinwheel Scheduling [ 30 ] implies that all instances with density bounded by 5/6 admit a