The pinwheel problem is NP-hard, implying hardness for related problems like bamboo garden trimming, and admits a PTAS that improves on the prior 9/7 approximation factor.
InProceedings of the 22nd Hawaii International Conference of System Science
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 2years
2026 2verdicts
UNVERDICTED 2roles
background 1polarities
background 1representative citing papers
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.
citing papers explorer
-
NP-Hardness and a PTAS for the Pinwheel Problem
The pinwheel problem is NP-hard, implying hardness for related problems like bamboo garden trimming, and admits a PTAS that improves on the prior 9/7 approximation factor.
-
Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
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.