2024/11/09 by Yuriy Biktairov, Biktairov, Yuriy, Leszek Gąsieniec +8 · 1 citation
Engineering · Social Sciences · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Islamic Finance and Communication #Marriage and Sexual Relationships #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.2411.06292
openalex publication_date 2024/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In Polyamorous Scheduling, 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 two different analyses of an approximation algorithm based on the Reduce-Fastest heuristic, from which we obtain first a 6-approximation and then a 5.24-approximation for Polyamorous Scheduling. We also strengthen the extant proof that there is no polynomial-time (1+δ)-approximation algorithm for the Optimisation Polyamorous Scheduling problem for any δ< \frac112 unless P = NP to the bipartite case. The decision version of Polyamorous Scheduling has a notion of density, similar to that of Pinwheel Scheduling, where problems with density below the threshold are guaranteed to admit a schedule (cf. the recently proven 5/6 conjecture, Kawamura, STOC 2024). We establish the existence of a similar threshold for Polyamorous Scheduling and give the first non-trivial bounds on the poly density threshold.