{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreieallbxln6qctbsmkhoza3j4jbi46ub2tolomhg4zb3hvxjswv22i",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjlo7he5fgt2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.13974v1",
  "publishedAt": "2026-04-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Robert Kleinberg",
    "Ahan Mishra"
  ],
  "textContent": "**Authors:** Robert Kleinberg, Ahan Mishra\n\nIn 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}$.",
  "title": "NP-Hardness and a PTAS for the Pinwheel Problem"
}