arXiv:2609.10641 · v3
A Deadline-Driven Algorithm for Polyamorous Scheduling
摘要
In Polyamorous Scheduling Problem, we are given an edge-weighted graph and must find a periodic schedule of matchings in this graph which minimizes the maximal weighted waiting time between consecutive occurrences of the same edge. This NP-hard problem generalises Bamboo Garden Trimming and is motivated by the need to find schedules of pairwise meetings in a complex social group. We present a $4 G^*$ algorithm for Polyamorous Scheduling, improving the previously known bound of $3 + \sqrt{5} \approx 5.236$. Our algorithm is inspired by the Deadline-Driven Heuristic which is optimal for Bamboo Garden Trimming (BGT).
作者备注：There is an error in section 2, right after the proof of Lemma 1. We claimed s <= 2(1/g_e - 1/g_f). This doesn't hold. Furthermore, the algorithm presented doesn't lead to constant bounded heat