  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, a
$O(\log \Delta)$-approximation for $\Delta$ 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.
