# The $2^k$ conjecture of Pinwheel Scheduling --- ### Pinwheel Scheduling $A = (a_1,\ldots,a_k)$  --- ### Pareto Surfaces Fix number of tasks $k$. Only finitely many “interesting” schedules:  --- ### Pareto Surfaces $k\le 5$  --- ### $2^k$ Conjecture **Our Conjecture:** Can solve all instances with $k$ tasks with maximum frequency $2^{k-1}$ --- ### Equivalent formulations  --- ### 5/6 Density Conjecture Density $d = \dfrac1{a_1}+\cdots+\dfrac1{a_k}$ Think: Fractional solution. Do $\frac1{a_i}$ fraction of task $i$ every day.  **Conjecture (1993):** $d\le \frac56$ implies schedule exists. --- ### Graph representation State = $(x_1,\ldots,x_k)$; $x_i$ = time since task $i$ Example for $(a_1,a_2,a_3) = (2,4,4)$ <!--  --> <img style="width:50%;" src="https://i.imgur.com/BQHcgyE.png"/> ---