Polyamorous Scheduling

• Published in 2024
• Added on 2024-04-10

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

• http://arxiv.org/abs/2403.00465v2
• http://arxiv.org/pdf/2403.00465v2

Other information

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-12-07},
	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}
}