Simple approximation algorithms for 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.
We introduced this problem in our FUN 2024 paper, alongside with a $O(\log n)$ approximation algorithm and a hardness-of-approximation reduction, showing that no polytime $(\frac43-\varepsilon)$-approximation exists unless P = NP.
Better approximation
In this paper, we show that the Reduce-Fastest($x$) algorithm known from the Bamboo Garden Trimming Problem can be adapted to Polyamorous Scheduling, yielding a simple constant-factor approximation.
Bipartite hardness
The hardness result in our FUN 2024 paper is based simply on the hardness of chromatic index, i.e., deciding whether a graph needs $\Delta$ or $\Delta+1$ colors in a proper edge coloring, where $\Delta$ is the maximum degree in the graph. This does not use the growth rates on the edges at all.
For the rather natural case of a polycule of heterosexual people, where the polyscheduling graph is bipartite, it is known that edge coloring is easy: one can always color the edges of a bipartite graph using $\Delta$ colors. Using a more involved reduction from 3SAT, we show that even for bipartite graphs, Polyamorous Scheduling is hard to approximate unless P = NP. Thus, we show that the hardness of Polyamorous Scheduling is not due to the edge coloring (alone), but rather due to the growth rates on the edges.
Poly density
Lastly, we make progress on the towards a simple density criterion for polyamorous schedule similar to the 5/6-threshold in Pinwheel Scheduling. We show that (1) up to a factor at most $\frac32$, the poly density is determined by the largest local density of any vertex, providing an easy-to-compute approximation for the poly density, and (2) we show that if poly density is $\le \frac14$, then a polyamorous schedule always exists (and can be computed in polynomial time).
This in particular means that Polyamorous Scheduling also has a density threshold $d^* \in [\frac14 ,\frac 56]$ below which a schedule always exists.