In the Polyamorous Scheduling Problem we are given an edge‑weighted graph and must construct a periodic sequence of matchings so that the maximum weighted waiting time between consecutive occurrences of the same edge is minimized. The problem is NP‑hard and generalizes the Bamboo Garden Trimming (BGT) problem, motivated by the need to schedule pairwise meetings in a complex social group. We present a $4 G^*$ algorithm that improves the previously known bound $3+\sqrt{5}\approx5.236$. The design is inspired by the deadline‑driven heuristic that is optimal for BGT, using the graph’s structure to select matchings before each deadline and thereby tighten the overall waiting‑time bound.
The algorithm proceeds in three main steps:
- Compute a deadline for each edge based on its weight;
- Traverse edges in non‑decreasing deadline order, greedily adding non‑conflicting edges to the current matching;
- Repeat until a full periodic schedule is formed.
Analysis shows that in the worst case the maximum weighted waiting time does not exceed $4 G^*$, achieving a substantial improvement over the prior bound.
Review