Pinwheel Covering
摘要
We want to find a schedule for several agents to take turns doing a job that must be done every day, where each agent i can work at most once in a specified number \(f _i\) of days. This problem, which we call Pinwheel Covering, can be viewed as a dual setting of the well-studied packing version of the Pinwheel Scheduling problem. We analyze the problem by applying the ideas used in the packing setting, including generalization of the problem to real-valued instances. We prove an asymptotic density guarantee, stating that there is a constant \(C > 0\) such that every instance \((f _1, \dots , f _n)\) with \(f _1 \le \dots \le f _n\) and \(1 / f _1 + \dots + 1 / f _n \ge 1 + C / \sqrt{f _1}\) is schedulable. We also study the computational complexity of related problems, and prove that the exact version of Pinwheel Covering is \(\textsf{NP}\) -hard. In fact, verifying a putative solution turns out to be already hard, a situation that stands in contrast to the packing setting.