# Polyamorous Scheduling

- Published in 2024
- Added on

In the collection

Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationships have different needs. We formally define and study the underlying optimisation problem: Polyamorous Scheduling. In Polyamorous Scheduling, we are given an edge-weighted graph and try to find a periodic schedule of matchings in this graph such that the maximal weighted waiting time between consecutive occurrences of the same edge is minimised. We show that the problem is NP-hard and that there is no efficient approximation algorithm with a better ratio than 4/3 unless P = NP. On the positive side, we obtain an $O(\log n)$-approximation algorithm; indeed, a $O(\log \Delta)$-approximation for $\Delta$ the maximum degree, i.e., the largest number of relationships of any individual. We also define a generalisation of density from the Pinwheel Scheduling Problem, "poly density", and ask whether there exists a poly-density threshold similar to the 5/6-density threshold for Pinwheel Scheduling [Kawamura, STOC 2024]. Polyamorous Scheduling is a natural generalisation of Pinwheel Scheduling with respect to its optimisation variant, Bamboo Garden Trimming. Our work contributes the first nontrivial hardness-of-approximation reduction for any periodic scheduling problem, and opens up numerous avenues for further study of Polyamorous Scheduling.

## Links

## Other information

- key
- PolyamorousScheduling
- type
- article
- date_added
- 2024-04-10
- date_published
- 2024-05-24

### BibTeX entry

@article{PolyamorousScheduling, key = {PolyamorousScheduling}, type = {article}, title = {Polyamorous Scheduling}, author = {Leszek G{\k{a}}sieniec and Benjamin Smith and Sebastian Wild}, abstract = {Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationships have different needs. We formally define and study the underlying optimisation problem: Polyamorous Scheduling. In Polyamorous Scheduling, we are given an edge-weighted graph and try to find a periodic schedule of matchings in this graph such that the maximal weighted waiting time between consecutive occurrences of the same edge is minimised. We show that the problem is NP-hard and that there is no efficient approximation algorithm with a better ratio than 4/3 unless P = NP. On the positive side, we obtain an {\$}O(\log n){\$}-approximation algorithm; indeed, a {\$}O(\log \Delta){\$}-approximation for {\$}\Delta{\$} the maximum degree, i.e., the largest number of relationships of any individual. We also define a generalisation of density from the Pinwheel Scheduling Problem, "poly density", and ask whether there exists a poly-density threshold similar to the 5/6-density threshold for Pinwheel Scheduling [Kawamura, STOC 2024]. Polyamorous Scheduling is a natural generalisation of Pinwheel Scheduling with respect to its optimisation variant, Bamboo Garden Trimming. Our work contributes the first nontrivial hardness-of-approximation reduction for any periodic scheduling problem, and opens up numerous avenues for further study of Polyamorous Scheduling.}, comment = {}, date_added = {2024-04-10}, date_published = {2024-05-24}, urls = {http://arxiv.org/abs/2403.00465v2,http://arxiv.org/pdf/2403.00465v2}, collections = {basically-computer-science}, url = {http://arxiv.org/abs/2403.00465v2 http://arxiv.org/pdf/2403.00465v2}, year = 2024, urldate = {2024-04-10}, archivePrefix = {arXiv}, eprint = {2403.00465}, primaryClass = {cs.DS} }