2026-07-23T16:50:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19923 2024-05-29T09:43:30Z ddc:004 open_access

Polyamorous Scheduling Gąsieniec, Leszek Smith, Benjamin Wild, Sebastian Periodic scheduling Pinwheel scheduling Edge-coloring Chromatic index Approximation algorithms Hardness of approximation Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationships have different needs. We formally define and study the underlying optimisation problem: Polyamorous Scheduling. In Polyamorous Scheduling, we are given an edge-weighted graph and try to find a periodic schedule of matchings in this graph such that the maximal weighted waiting time between consecutive occurrences of the same edge is minimised. We show that the problem is NP-hard and that there is no efficient approximation algorithm with a better ratio than 4/3 unless P = NP. On the positive side, we obtain an O(log n)-approximation algorithm; indeed, an O(log Δ)-approximation for Δ the maximum degree, i.e., the largest number of relationships of any individual. We also define a generalisation of density from the Pinwheel Scheduling Problem, "poly density", and ask whether there exists a poly-density threshold similar to the 5/6-density threshold for Pinwheel Scheduling [Kawamura, STOC 2024]. Polyamorous Scheduling is a natural generalisation of Pinwheel Scheduling with respect to its optimisation variant, Bamboo Garden Trimming. Our work contributes the first nontrivial hardness-of-approximation reduction for any periodic scheduling problem, and opens up numerous avenues for further study of Polyamorous Scheduling. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leszek Gąsieniec and Benjamin Smith and Sebastian Wild 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.15 urn:nbn:de:0030-drops-199234 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.15 eng https://creativecommons.org/licenses/by/4.0/legalcode