{
  "abstract": "In the pinwheel scheduling problem, each task i is associated with a positive integer ai called its period, and we want to (perpetually) schedule one task per day so that each task i is performed at least once every ai days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates 1/ai, does not exceed 1. We prove that all instances with density not exceeding 5/6 are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress toward the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (noninteger) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most 1 is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio 4/3.",
  "abstract_shown": true,
  "affiliations": [
    "Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan"
  ],
  "article_type": "research article",
  "arxiv": null,
  "author_total": 1,
  "authors": [
    {
      "affs": [
        0
      ],
      "name": "Akitoshi Kawamura",
      "orcid": "0009-0006-3706-7470"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/ec5x599111d49.bib",
  "cited_by": 0,
  "doi": "10.1073/pnas.2530214123",
  "fulltext_url": "https://pmc.ncbi.nlm.nih.gov/articles/PMC13462934/",
  "id": "ec5x599111d49",
  "issns": [
    "0027-8424",
    "1091-6490"
  ],
  "landing_url": "https://doi.org/10.1073/pnas.2530214123",
  "language": "en",
  "licence": "CC-BY-NC-ND-4.0",
  "licence_label": "CC BY-NC-ND 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by-nc-nd/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "heading",
      "421"
    ],
    [
      "heading",
      "Mathematics"
    ],
    [
      "heading",
      "Physical Sciences"
    ],
    [
      "openalex",
      "2209|Scheduling and Optimization Algorithms"
    ]
  ],
  "openalex": "W7201851424",
  "pdf_url": null,
  "pmcid": "PMC13462934",
  "pmid": "42566470",
  "published": "2026-08-07",
  "publisher": "National Academy of Sciences",
  "ris": "https://research.draconitic.com/paper/ec5x599111d49.ris",
  "sources": [
    {
      "first_seen": "2026-11-01T12:23:32Z",
      "native_id": "PMC13462934",
      "source": "pmc",
      "url": "https://doi.org/10.1073/pnas.2530214123"
    }
  ],
  "subjects": [
    {
      "field": "biochemistry",
      "origin": "journal-openalex:1312|Genomics and Chromatin Dynamics",
      "subfield": "molecular-biology"
    }
  ],
  "title": "Proof of the density threshold conjecture for pinwheel scheduling",
  "title_text": "Proof of the density threshold conjecture for pinwheel scheduling",
  "type": "peer-reviewed",
  "updated_at": "2026-11-02T12:20:46Z",
  "url": "https://research.draconitic.com/paper/ec5x599111d49",
  "venue": "Proceedings of the National Academy of Sciences of the United States of America",
  "versions": []
}