{"ID":2897991,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04537","arxiv_id":"2507.04537","title":"The Fair Periodic Assignment Problem","abstract":"We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a O(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a O(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.","short_abstract":"We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a O(n log n) algorithm to solve this problem. Next, we fo...","url_abs":"https://arxiv.org/abs/2507.04537","url_pdf":"https://arxiv.org/pdf/2507.04537v1","authors":"[\"Rolf van Lieshout\",\"Bart van Rossum\"]","published":"2025-07-06T21:06:59Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.OC\"]","methods":"[]","has_code":false}