“Polyamorous Scheduling”, Leszek Gąsieniec, Benjamin Smith, Sebastian Wild2024-03-01 (algorithms, STEM humor)⁠:

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 optimization 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 minimized. We show that the problem is NP-hard and that there is no efficient approximation algorithm with a better ratio than 13⁄12 unless p = NP. On the positive side, we obtain an 𝒪(log n)-approximation algorithm. We also define a generalization 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 (Kawamura2023). Polyamorous Scheduling is a natural generalization of Pinwheel Scheduling with respect to its optimization variant, Bamboo Garden Trimming [see also Kuszmaul2022].

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.