Simple approximation algorithms for Polyamorous Scheduling

Biktairov, Y, Gąsieniec, L ORCID: 0000-0003-1809-9814, Jiamjitrak, WP, Namrata, Smith, B and Wild, S ORCID: 0000-0002-6061-9177 (2025) Simple approximation algorithms for Polyamorous Scheduling. In: SIAM Symposium on Simplicity in Algorithms (SOSA25), 2025-1-13 - 2024-10-14, New Orleans.

Text SOSA - paper 126.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (816kB) | Preview

Abstract

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 δ < 1/12 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.

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:	29 Oct 2024 08:27
Last Modified:	09 Jun 2025 14:31
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3186293