Biktairov, Yuriy, Gąsieniec, Leszek, Jiamjitrak, Wanchote Po, Namrata, Smith, Benjamin and Wild, Sebastian 
ORCID: 0000-0002-6061-9177
(2024)
Simple approximation algorithms for Polyamorous Scheduling.
[Preprint]
|
PDF
2411.06292v1.pdf - Preprint version Download (891kB) | 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+\delta)$-approximation algorithm for the Optimisation Polyamorous Scheduling problem for any $\delta < \frac1{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: | Preprint |
|---|---|
| Additional Information: | accepted at SOSA 2025. arXiv admin note: text overlap with arXiv:2403.00465 |
| Uncontrolled Keywords: | cs.DS, cs.DS, cs.CC |
| 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: | 25 Nov 2024 09:27 |
| Last Modified: | 13 Dec 2024 13:47 |
| DOI: | 10.48550/arxiv.2411.06292 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3188868 |
Altmetric
Altmetric
