pipette
ENEnglish

A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel Scheduling

Hiroshi Fujiwara, Grzegorz Gutowski, Katsuhisa Ouchi, Alexander Wolff

Preprint

En palabras de los autores

In pinwheel scheduling with real periods, an instance consists of tasks with real periods . The goal is to find a schedule that assigns one task to each day indefinitely such that, for every task and every positive integer , task occurs at least times in every block of consecutive days. Given an instance , its dimension is , its density is , and its potential is . We prove that every real-valued instance of density at most 5/6 admits a periodic schedule of period length less than . For integer periods, the 5/6 density bound was a long-standing conjecture settled by Kawamura using a computer-assisted proof [STOC 2024, PNAS 2026]. Our result confirms the real-period conjecture of Fujiwara, Miyagi, and Ouchi [DMTCS 2026]. Our computer-assisted proof builds on Kawamura's ideas while using fewer explicit schedules. It combines dimension reduction by folding with nine satisfiability modulo theories (SMT) checks over linear real arithmetic. A set of 14287 explicit periodic schedules contains a schedule for every instance of dimension at most 8 and density at most 5/6, and for every instance of dimension 9 and potential at most 5/6. Folding is used to reduce every instance of larger dimension and potential at most 5/6 to an instance of dimension 9 and the same potential bound. We also prove that every real-valued instance with minimum period at least 4 and density at most 17/20=0.85 admits a periodic schedule of period length less than . The density bound 17/20 is tight and improves the 0.84-bound of Mishra, Rho, and Kleinberg [arXiv 2025] for integer periods. It also resolves the case of Kawamura's 2025 conjecture that integer-valued instances of density at most are schedulable.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.