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.
Figure: The example poly scheduling instance from Fig. 1. The top left: Graph representation with edge labels showing the desire growth rates of each pairwise relationship. Bottom: An optimal schedule for the instance with period 8. Top right: The (feasible) decision version of the instance obtained for heat 160. The edge labels here are the frequencies with which edges have to be scheduled stay below heat 160.
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.