Source-linked AI summary
A Deadline-Driven Algorithm for Polyamorous Scheduling
Arjun Maneesh Agarwal
TL;DR
Polyamorous Scheduling asks for daily matchings that minimize the maximum edge heat over an infinite horizon. The paper adapts BGT's deadline-based idea to the matching setting and proves a strict heat bound below 4G* for its deadline-ordered greedy maximal matching.
Problem
Polyamorous Scheduling seeks daily matchings that minimize the supremum heat over an infinite horizon.
Source: §1 · p. 1Method
Results
The deadline-ordered greedy maximal matching achieves heat strictly below 4G*.
Source: §2 · p. 5Takeaways & Limitations
The paper establishes a strict 4G* heat guarantee for its deadline-based approach to Polyamorous Scheduling.
Source: §1 · p. 2, §2 · p. 5The analysis usually normalizes graph growth to G*=1.
Source: §1 · p. 2
Abstract
from arXiv · showhide
In Polyamorous Scheduling Problem, 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 a $4 G^*$ algorithm for Polyamorous Scheduling, improving the previously known bound of $3 + \sqrt{5} \approx 5.236$. Our algorithm is inspired by the Deadline-Driven Heuristic which is optimal for Bamboo Garden Trimming (BGT).
1 Background and Motivation
Polyamorous Scheduling assigns growing heat to graph edges and seeks daily matchings that minimize the maximum heat over an infinite horizon. The paper motivates a deadline-based approach by connecting the problem to Bamboo Garden Trimming, whose star-graph case has an optimal deadline-driven strategy.
1 Background and Motivation
- The objective is to choose a matching each day to minimize the supremum heat over an infinite horizon.Each relationship edge has a positive growth rate, and its heat resets when scheduled.Source: §1 · p. 1
- The paper usually normalizes graph growth to G*=1.Source: §1 · p. 2
- When the graph is a star, the problem is exactly Bamboo Garden Trimming, with each edge behaving like a growing bamboo stalk.Scheduling an edge resets its height.Source: §1 · p. 2
- Kuszmaul (2022)[3] shows that a greedy Deadline-Driven Strategy achieves the optimal worst-case backlog of 2 by trimming the bamboo of height at least 1 predicted to reach height 2 soonest if left untrimmed.Source: §1 · p. 2
- The general graph problem is harder because each day's schedule must be a matching rather than a single choice, motivating a direct transfer of BGT's deadline idea.Source: §1 · p. 2
2 The Deadline-Driven Matching Algorithm
The algorithm orders eligible edges by deadline and greedily builds a matching each day. Its deadline-ordered greedy maximal matching achieves heat strictly below 4G*.
2 The Deadline-Driven Matching Algorithm
- An edge with heat at least 1 is assigned the predicted time it would reach the critical value if left unserviced.Source: §2 · p. 2
- Each day, the algorithm scans eligible edges by non-decreasing deadline and adds an edge only when neither endpoint is already matched.The selected matching is scheduled that day, and its edges rest.Source: §2 · p. 3
- If an eligible edge is omitted from the matching, an earlier-scanned selected edge incident to it serves as a witness.The proof fixes one witness per day and limits its use to the time before it expires as a usable witness.Source: §2 · pp. 3–4
- The proof bounds eligible-but-unscheduled days and converts that count into an edge-heat bound before restoring the G* normalization.Source: §2 · p. 5
- The deadline-ordered greedy maximal matching achieves heat strictly below 4G*.Source: §2 · p. 5