2026-10-01T23:07:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24955 2026-09-23T23:22:42Z ddc:004 open_access

Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems Kobayashi, Yusuke Lin, Bingkai Pinwheel Scheduling Polynomial-time Solvability Packing and Covering Fixed Parameter Algorithms In the Pinwheel Packing problem, we are given a set of recurring tasks, each associated with a positive integer a_i for task i. The objective is to select one task to perform each day such that every task i is performed at least once within every a_i consecutive days. The exact computational complexity of this problem, where ∑ 1/a_i = 1, has remained an open question for more than 30 years; in particular, it is still unknown whether the problem is NP-hard. The first contribution of this paper is to show that Pinwheel Packing cannot be solved in polynomial time under a standard complexity assumption, improving upon the hardness result shown by Jacobs and Longo. Additionally, we present fixed-parameter algorithms for variants of Pinwheel Packing, parameterized by the number of tasks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yusuke Kobayashi and Bingkai Lin 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.47 urn:nbn:de:0030-drops-249558 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.47 eng https://creativecommons.org/licenses/by/4.0/legalcode