{"ID":2894542,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.11681","arxiv_id":"2507.11681","title":"Finite Pinwheel Scheduling: the k-Visits Problem","abstract":"Pinwheel Scheduling is a fundamental scheduling problem, in which each task $i$ is associated with a positive integer $d_i$, and the objective is to schedule one task per time slot, ensuring each task perpetually appears at least once in every $d_i$ time slots. Although conjectured to be PSPACE-complete, it remains open whether Pinwheel Scheduling is NP-hard (unless a compact input encoding is used) or even contained in NP. We introduce k-Visits, a finite version of Pinwheel Scheduling, where given n deadlines, the goal is to schedule each task exactly k times. While we observe that the 1-Visit problem is trivial, we prove that 2-Visits is strongly NP-complete through a surprising reduction from Numerical 3-Dimensional Matching (N3DM). As intermediate steps in the reduction, we define NP-complete variants of N3DM which may be of independent interest. We further extend our strong NP-hardness result to a generalization of k-Visits $k\\geq 2$ in which the deadline of each task may vary throughout the schedule, as well as to a similar generalization of Pinwheel Scheduling, thus making progress towards settling the complexity of Pinwheel Scheduling. Additionally, we prove that 2-Visits can be solved in linear time if all deadlines are distinct, rendering it one of the rare natural problems which exhibit the interesting dichotomy of being in P if their input is a set and NP-complete if the input is a multiset. We achieve this through a Turing reduction from 2-Visits to a variation of N3DM, which we call Position Matching. Based on this reduction, we also show an FPT algorithm for 2-Visits parameterized by a value related to how close the input deadlines are to each other, as well as a linear-time algorithm for instances with up to two distinct deadlines.","short_abstract":"Pinwheel Scheduling is a fundamental scheduling problem, in which each task $i$ is associated with a positive integer $d_i$, and the objective is to schedule one task per time slot, ensuring each task perpetually appears at least once in every $d_i$ time slots. Although conjectured to be PSPACE-complete, it remains ope...","url_abs":"https://arxiv.org/abs/2507.11681","url_pdf":"https://arxiv.org/pdf/2507.11681v2","authors":"[\"Sotiris Kanellopoulos\",\"Christos Pergaminelis\",\"Maria Kokkou\",\"Euripides Markou\",\"Aris Pagourtzis\"]","published":"2025-07-15T19:36:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}