pith. machine review for the scientific record. sign in

arxiv: 2604.13974 · v1 · submitted 2026-04-15 · 💻 cs.DS · cs.CC

Recognition: unknown

NP-Hardness and a PTAS for the Pinwheel Problem

Robert Kleinberg , Ahan Mishra
Authors on Pith no claims yet

Pith reviewed 2026-05-10 12:00 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords pinwheel problemNP-hardnessPTASschedulingapproximation algorithmscomputational complexityreduction
0
0 comments X

The pith

The pinwheel problem is NP-hard, and an approximate version admits a PTAS.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the pinwheel problem is NP-hard, settling an open question first posed in 1989. Given positive integers a1 through am, the task is to decide whether they can be partitioned into color classes C1 through Cm such that each Ci meets every interval of length ai. The hardness proof is by direct polynomial-time reduction from a known NP-complete problem and immediately implies the same for pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. On the algorithmic side, the authors give a polynomial-time approximation scheme for a natural relaxation of the problem, beating the previous best factor of 9/7.

Core claim

The pinwheel problem is NP-hard. This is established by a polynomial-time reduction from an NP-complete problem that preserves the yes/no answer, and the same reduction technique shows NP-hardness for pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. Separately, an approximate version of the pinwheel problem, in which the interval intersection condition is relaxed, admits a polynomial-time approximation scheme.

What carries the argument

A polynomial-time reduction from a known NP-complete problem that maps instances to m-tuples (a1,...,am) while preserving the property that a valid coloring exists if and only if the source instance is yes.

If this is right

  • Pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem are all NP-hard.
  • No polynomial-time exact algorithm exists for the pinwheel problem unless P=NP.
  • The PTAS gives arbitrarily good polynomial-time approximations for the relaxed pinwheel problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practical scheduling systems that rely on pinwheel-type periodic constraints will need to use heuristics or accept approximate solutions in the worst case.
  • The reduction technique may be adaptable to prove hardness for other interval-coloring or density-constrained scheduling variants.

Load-bearing premise

The reduction correctly maps yes-instances to yes-instances and no-instances to no-instances of the pinwheel decision problem.

What would settle it

A polynomial-time algorithm that correctly decides the pinwheel problem on every input tuple of positive integers would falsify the NP-hardness claim.

Figures

Figures reproduced from arXiv: 2604.13974 by Ahan Mishra, Robert Kleinberg.

Figure 2
Figure 2. Figure 2: Density Flow Graph. Note that 𝑐 = clause_sum and 𝑟 𝑠𝑖 is the remaining space in the subschedule of variable 𝑥𝑖 Note that this algorithm will be used for each variable to leave density within each subschedule that is exactly enough for all the clauses to be scheduled within it [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Warm Greedy Job Addition. An amount of density equal to [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
read the original abstract

In the pinwheel problem, one is given an $m$-tuple of positive integers $(a_1, \ldots, a_m)$ and asked whether the integers can be partitioned into $m$ color classes $C_1,\ldots,C_m$ such that every interval of length $a_i$ has non-empty intersection with $C_i$, for $i = 1, 2, \ldots, m$. It was a long-standing open question whether the pinwheel problem is NP-hard. We affirm a prediction of Holte et al. (1989) by demonstrating, for the first time, NP-hardness of the pinwheel problem. This enables us to prove NP-hardness for a host of other problems considered in the literature: pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. On the positive side, we develop a PTAS for an approximate version of the pinwheel problem. Previously, the best approximation factor known to be achievable in polynomial time was $\frac{9}{7}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves NP-hardness of the pinwheel problem (given m-tuple of positive integers, decide if they can be partitioned into color classes satisfying the interval intersection condition) via a polynomial-time reduction, affirming the 1989 prediction of Holte et al. It transfers this hardness to pinwheel covering, bamboo garden trimming, windows scheduling, recurrent scheduling, and the constant gap problem. On the algorithmic side, it gives a PTAS for an approximate version of the pinwheel problem, improving the prior best polynomial-time ratio of 9/7.

Significance. Resolving the long-standing open question on the complexity of the pinwheel problem is a notable contribution to scheduling theory and combinatorial optimization. The hardness results unify several related problems under a single reduction, while the PTAS provides the first constant-factor improvement beyond 9/7 and is a practical advance for approximation algorithms in this domain. The explicit construction of the reduction and the PTAS are the primary strengths.

minor comments (3)
  1. The abstract states the NP-hardness and PTAS results but provides no high-level outline of the reduction source problem or the PTAS construction technique; adding one sentence on each would improve accessibility without lengthening the abstract unduly.
  2. Section 3 (reduction) and Section 5 (PTAS) would benefit from a brief comparison table listing the new approximation ratio against the prior 9/7 bound and against trivial baselines, to make the improvement quantitative at a glance.
  3. Notation for the color classes C_i and the interval condition is introduced clearly in the abstract but re-defined with slight variations in the preliminaries; a single consolidated definition early in Section 2 would prevent minor reader confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our contributions, and recommendation of minor revision. We are pleased that the significance of resolving the 1989 open question and unifying hardness results across related scheduling problems is recognized.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via external reduction

full rationale

The central claim is NP-hardness of the pinwheel problem, established by a new polynomial-time reduction from a known NP-complete problem (independent of any prior result by these authors). The PTAS is presented as a separate algorithmic contribution. The sole citation to Holte et al. (1989) is used only to identify the open question being resolved, not as load-bearing justification for the proof. No self-definitional steps, fitted parameters renamed as predictions, or ansatzes smuggled via self-citation appear in the derivation chain. The reduction is described as preserving yes/no instances in polynomial time, with no reduction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on a standard complexity reduction whose specific construction and correctness are not detailed in the abstract; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption The pinwheel problem is polynomial-time reducible from a known NP-complete problem.
    This is the core mechanism for establishing NP-hardness, but the reduction details are not provided.

pith-pipeline@v0.9.0 · 5482 in / 1210 out tokens · 47842 ms · 2026-05-10T12:00:48.066831+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants

    cs.DS 2026-04 unverdicted novelty 7.0

    2-Visits is strongly NP-complete for multiplicity 2 but in RP for constant distinct deadlines, with a 0.9142 density lower bound for 2-Visits and thresholds approaching 5/6 for large k.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    WindowsSchedulingProblemsforBroadcastSystems.SIAM J

    AmotzBar-NoyandRichardE.Ladner.2003. WindowsSchedulingProblemsforBroadcastSystems.SIAM J. Comput.32, 4 (2003), 1091–1113. doi:10.1137/S009753970240447X2, 19 AmotzBar-Noy,RichardELadner,andTamiTamir.2007. Windowsschedulingasarestrictedversionofbin packing.ACMTransactionsonAlgorithms(TALG)3,3(2007),28–es. doi:10.1145/1273340.1273344 1, 3, 9, 19 Federico Della Croce

    work page doi:10.1137/s009753970240447x2 2003

  2. [2]

    arXiv:2003.12460 [cs.DS]https://arxiv.org/abs/2003.124602 39 Charles-Jean de la Vallée Poussin

    An enhanced pinwheel algorithm for the bamboo garden trimming problem. arXiv:2003.12460 [cs.DS]https://arxiv.org/abs/2003.124602 39 Charles-Jean de la Vallée Poussin

    work page arXiv 2003

  3. [3]

    Annales de la Société scientifique de Bruxelles20 (1896), 183–256

    Recherches analytiques sur la théorie des nombres premiers. Annales de la Société scientifique de Bruxelles20 (1896), 183–256. doi:10.1017/978100950452232 Hiroshi Fujiwara, Kota Miyagi, and Katsuhisa Ouchi

    work page doi:10.1017/978100950452232

  4. [4]

    In SOFSEM 2026: Theory and Practice of Computer Science, Jakub Kozik and Alexander Wolff (Eds.)

    Pinwheel Scheduling with Real Periods. In SOFSEM 2026: Theory and Practice of Computer Science, Jakub Kozik and Alexander Wolff (Eds.). Springer Nature Switzerland, Cham, 621–633. doi:10.1007/978-3-032-17801-5_456 Leszek G˛ asieniec, Tomasz Jurdziński, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and TomaszRadzik.2024.Perpetualmaintenanceo...

    work page doi:10.1007/978-3-032-17801-5_456 2026

  5. [5]

    InApproximation, Randomization, and Combinatorial Optimiza- tion

    A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs. InApproximation, Randomization, and Combinatorial Optimiza- tion. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023 (LIPIcs, Vol. 275), Nicole Megow and Adam D. Smith (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Atlanta, Georgi...

    work page doi:10.4230/lipics.approx/random.2023.162 2023

  6. [6]

    InProceedings of the 22nd Hawaii International Conference of System Science

    The pinwheel: A real-time scheduling problem. InProceedings of the 22nd Hawaii International Conference of System Science. IEEE, Hawaii, USA, 693–702. doi:10.1109/HICSS.1989.48075, 1, 4, 5, 6, 7, 17, 18, 20, 21, 27, 28, 29 Tobias Jacobs and Salvatore Longo. 2014.A new perspective on the windows scheduling problem. arXiv:1410.7237 doi:10.48550/arXiv.1410.7...

    work page doi:10.1109/hicss.1989.48075 1989

  7. [7]

    InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing(Vancouver, BC, Canada)(STOC 2024).AssociationforComputingMachinery,NewYork,NY,USA,1816–1819

    Proof of the Density Threshold Conjecture for Pinwheel Scheduling. InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing(Vancouver, BC, Canada)(STOC 2024).AssociationforComputingMachinery,NewYork,NY,USA,1816–1819. doi:10.1145/3618260. 36497571, 2, 4, 9, 25, 30, 36, 37, 38 Akitoshi Kawamura, Yusuke Kobayashi, and Yosuke Kusano

    work page doi:10.1145/3618260 2024

  8. [8]

    InAlgorithms and Complexity, IreneFinocchiandLoukasGeorgiadis(Eds.).SpringerNatureSwitzerland, Cham, 185–199

    Pinwheel Covering. InAlgorithms and Complexity, IreneFinocchiandLoukasGeorgiadis(Eds.).SpringerNatureSwitzerland, Cham, 185–199. doi:10.1007/s00453-002-0938-92, 6, 9, 17, 20, 27, 29, 34 40 Akitoshi Kawamura and Makoto Soejima

    work page doi:10.1007/s00453-002-0938-92

  9. [9]

    doi:10.1016/j.tcs.2020.07.03717 DavidKempe,LeonardJSchulman,andOmerTamuz.2018

    Simple strategies versus optimal schedules in multi-agent patrolling.TheoreticalComputerScience839(2020),195–206. doi:10.1016/j.tcs.2020.07.03717 DavidKempe,LeonardJSchulman,andOmerTamuz.2018. Quasi-regularsequencesandoptimalschedules for security games. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, New Orleans,...

    work page doi:10.1016/j.tcs.2020.07.03717 2020

  10. [10]

    In2018 IEEE 59th Annual Symposium onFoundationsofComputerScience(FOCS).IEEE,Paris,France,309–319

    Recharging Bandits. In2018 IEEE 59th Annual Symposium onFoundationsofComputerScience(FOCS).IEEE,Paris,France,309–319. doi:10.1109/FOCS.2018. 000372, 5, 19 Donald E. Knuth

    work page doi:10.1109/focs.2018 2018

  11. [11]

    1126/science.194.4271.12355 YusukeKobayashiandBingkaiLin.2025

    Mathematics and Computer Science: Coping with Finiteness.Science194, 4271(1976),1235–1242.arXiv:https://www.science.org/doi/pdf/10.1126/science.194.4271.1235doi:10. 1126/science.194.4271.12355 YusukeKobayashiandBingkaiLin.2025. HardnessandFixedParameterTractabilityforPinwheelSchedul- ing Problems. In36th International Symposium on Algorithms and Computati...

    work page doi:10.1126/science.194.4271.1235doi:10 1976

  12. [12]

    359), Ho-Lin Chen, Wing-Kai Hon, and Meng- Tsung Tsai (Eds.)

    (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 359), Ho-Lin Chen, Wing-Kai Hon, and Meng- Tsung Tsai (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 47:1–47:15. doi:10.4230/LIPIcs.ISAAC.2025.471 Jan Korst, Emile Aarts, and Jan Karel Lenstra

    work page doi:10.4230/lipics.isaac.2025.471 2025

  13. [13]

    1 WieslawKubiak.2004

    Scheduling periodic tasks.INFORMS journal on Computing8, 4 (1996), 428–435. 1 WieslawKubiak.2004. FairSequences. InHandbookofScheduling: Algorithms,Models,andPerformance Analysis, Joseph Y-T. Leung and James H. Anderson (Eds.). CRC Press, Boca Raton, FL, Chapter 26, 430–450. doi:10.1201/97802034898022, 19 WieslawKubiak.2009.ProportionalOptimizationandFair...

    work page doi:10.1201/97802034898022 1996

  14. [14]

    doi:10.1007/978-0-387-87719-819 Ahan Mishra

    Springer, New York, NY. doi:10.1007/978-0-387-87719-819 Ahan Mishra. 2026.An Optimal Density Bound for Discretized Point Patrolling. SIAM, Vancouver, BC, Canada, 2846–2875. doi:10.1137/1.9781611978971.1052 Al Mok, Louis Rosier, Igor Tulchinsky, and Donald Varvel

    work page doi:10.1007/978-0-387-87719-819 2026

  15. [15]

    doi:10.1016/0165-6074(89)90128-2Fifteenth EUROMICRO Symposium on Microprocessing and Microprogramming

    Algorithms and complexity of the periodic maintenance problem.Microprocessing and Microprogramming27, 1 (1989), 657–664. doi:10.1016/0165-6074(89)90128-2Fifteenth EUROMICRO Symposium on Microprocessing and Microprogramming. 3, 7, 8, 28, 29 Timothy P Novikoff, Jon M Kleinberg, and Steven H Strogatz

    work page doi:10.1016/0165-6074(89)90128-2fifteenth 1989

  16. [16]

    Reconstructing Waddington’s landscape from data

    Education of a model student. Proceedings of the National Academy of Sciences109, 6 (2012), 1868–1873. doi:10.1073/pnas. 11098631091 J.BarkleyRosserandLowellSchoenfeld.1962. Approximateformulasforsomefunctionsofprimenumbers. Illinois Journal of Mathematics6, 1 (1962), 64 –

    work page doi:10.1073/pnas 2012

  17. [17]

    doi:10.1215/ijm/125563180710, 31 Craig A. Tovey

    work page doi:10.1215/ijm/125563180710

  18. [18]

    doi:10.1016/0166-218X(84)90081-710 MartijnvanEe.2021

    A simplified NP-complete satisfiability problem.Discrete Applied Mathematics8, 1 (1984), 85–89. doi:10.1016/0166-218X(84)90081-710 MartijnvanEe.2021. A12/7-approximationalgorithmforthediscreteBambooGardenTrimmingproblem. Operations Research Letters49, 5 (2021), 645–649. doi:10.1016/j.orl.2021.07.0012 W.DWeiandC.LLiu.1983. Onaperiodicmaintenanceproblem.Ope...

    work page doi:10.1016/0166-218x(84)90081-710 1984