Polyamorous Scheduling


Gąsieniec, L, Smith, B and Wild, S ORCID: 0000-0002-6061-9177 (2024) Polyamorous Scheduling. .

Access the full-text of this item by clicking on the Open Access link.

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, an O(log ∆)-approximation for ∆ 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.

Item Type: Conference Item (Unspecified)
Divisions: Faculty of Science and Engineering
Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 26 Sep 2024 15:55
Last Modified: 07 Jun 2025 17:21
DOI: 10.4230/LIPIcs.FUN.2024.15
Open Access URL: https://doi.org/10.4230/LIPIcs.FUN.2024.15
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3184760
Altmetric
CORE (COnnecting REpositories)