Polyamorous Scheduling

In *Polyamorous Scheduling*, the task is to find a periodic schedule for
the edges of a graph, where each day we can schedule a matching in the graph,
so that we minimize the maximal height any edge’s desire grows to, the “heat”,
where every edge has a daily desire growth rate.

This models a polycule of people with pairwise relationships (of different emotional weight) who want to find a schedule for all couples.

## Results

We give a simple $O(\log(\Delta))$-approximation algorithm, where $\Delta$ is the largest degree in the graph, and we show a fun reduction from MAX-3SAT. We establish that Poly Scheduling doesn’t allow an efficient $(\frac{4}{3}-\varepsilon)$-approximation (unless $\mathrm{P} = \mathrm{NP}$).

*Update:* The original version of the manuscript had a weaker inapproximability result, but we found a simple way to obtain the stronger one quoted above.

We also define a generalization of the notion of *density* in Pinwheel Scheduling for poly scheduling and ask whether there can be an analog of the $\frac{5}{6}$-density threshold.