A Deadline-Driven Algorithm for Polyamorous Scheduling
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A Deadline-Driven Algorithm for Polyamorous Scheduling".
Jane: Here's the gist of the paper. 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 Problem Definition and Motivation The Polyamorous Scheduling problem involves finding a periodic schedule of matchings in an edge-weighted graph to minimize the supremum heat over an infinite horizon The objective is to minimize heat(schedule) = sup e∈E, t≥0 he(t).
Tom: A natural normalization sets the growth rate of the graph G to be G∗ = max v∈P Gv, and it is clear that OPT ≥ G∗ for all instances.
Jane: The special case where G = (P, E) is a star is exactly the classical bamboo garden trimming problem (BGT).
Tom: Deadline-Driven Matching Algorithm The Deadline-Driven Matching algorithm defines a deadline for an edge e with growth rate ge and current heat he(t) ≥ 1 as Dt(e) = t + 2 − he(t) / ge.
Paper summary: Jane: We just touched on how this approach works conceptually, but let's get a clearer picture of what "A Deadline-Driven Algorithm for Polyamorous Scheduling" is trying to solve in detail.
Lu: The paper starts by defining the setup, which is an edge-weighted graph G with a set of people P, where each edge represents a relationship and has a positive growth rate.
Tom: Each edge carries a heat score at time t that increases at the rate of its growth rate if it isn't scheduled, and it resets to zero whenever the edge is scheduled.
Jane: The main objective they are aiming for is minimizing the maximal weighted waiting time between consecutive occurrences of the same edge over an infinite horizon.
Lalam: The authors introduce a natural normalization, saying that given the growth rate of a vertex v is G v equals X times its growth rate ge, then they define the growth rate of the graph as G star equals max v in P G v.
Tom: They establish that it’s clear that the optimal result, OPT, must be greater than or equal to this graph growth rate, so OPT is at least G star for any instance.
Jane: They point out that a special case of this problem where the graph is just a star—meaning one central person connected to everyone—is exactly the classical Bamboo Garden Trimming Problem.
Lu: Kuszmaul’s work shows that in that single-stalk case, a greedy Deadline-Driven Strategy can actually achieve an optimal worst-case backlog of two.
Tom: But they emphasize that the general graph version, Polyamorous Scheduling Problem, is considerably harder because a day’s schedule must be a matching rather than just picking one single choice.
Jane: This is where the complexity kicks in, and the paper then introduces their own algorithm inspired by BGT.
Lalam: They present an algorithm called Reduce-Fastest from Biktairov and others, which orders edges by decreasing growth rate and greedily matches those whose heat exceeds a threshold x times G star.
Tom: The value they set for that threshold is x equals two plus two over the square root five divided by five, which gives them a three plus square root five approximation ratio.
Jane: Now, this paper’s main contribution is trying to import that deadline-based idea directly into the Polyamorous Scheduling Problem and see if it yields a better bound than that previous result.
Lu: Their main theorem states that the deadline-ordered greedy maximal matching actually achieves a heat strictly less than four times G star.
Tom: That means they improved the known approximation ratio from something around five point two three six down to something related to four times G star.
Conclusion: Jane: So, wrapping up this discussion on "A Deadline-Driven Algorithm for Polyamorous Scheduling," we’ve seen how they use a deadline-based matching strategy to tackle the challenge of minimizing waiting time in these scheduling problems.
Tom: The title itself suggests that they are focusing on the deadline aspect, and what it means is that the timing of when an edge becomes eligible is what drives their selection process for matchings.
Lu: It’s interesting because it shows that a technique proven optimal for a simpler structure, like trimming a bamboo stalk, can actually be useful in a much more complicated setting like matching edges in an arbitrary graph.
Meng: So, what does this mean when we look at deploying these kinds of models on real traffic? Does it suggest that our scheduling algorithms will inherently perform better under dynamic constraints?
Tom: It suggests that by focusing the greedy choice on edges that are about to exceed their deadline, you’re making a locally optimal decision that leads to a globally better schedule over the long run.
Jane: The authors have successfully shown they can import this deadline-based intuition and get a tighter bound than what was previously known for these types of problems.
Lalam: It gives us more confidence that we can use heuristics inspired by simpler, well-understood problems to tackle much larger and more complex scheduling challenges in the real world.
Chennai Mathematical Institute
cs.DS
Submitted: 2026-09-09
Updated: 2026-11-02
Comments: There is an error in section 2, right after the proof of Lemma 1. We claimed s <= 2(1/g_e - 1/g_f). This doesn't hold. Furthermore, the algorithm presented doesn't lead to constant bounded heat
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 73/100
The gist: 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…
Key concepts
- Polyamorous Scheduling Problem
- This is a problem where you have an edge-weighted graph and need to create a repeating schedule of matchings. The goal is to make sure that no single edge waits too long before it appears again in the schedule, aiming to minimize this maximum waiting time over an infinite time horizon.
- Deadline-Driven Matching Algorithm
- This is a specific scheduling procedure. For any eligible edge, it calculates a deadline based on its growth rate and current heat. The matching for that day is then chosen by selecting edges with the earliest deadlines first, ensuring that edges are scheduled before they become too 'late'.
- Heat Function (he(t))
- The heat function measures how much an edge has waited since its last occurrence. If the heat of an edge is greater than 1, it becomes eligible for scheduling. The algorithm uses this value to determine the deadline, which helps manage and reduce the accumulated waiting time for each specific edge.
- Witness Lemma
- This lemma is a key proof tool showing that if an edge isn't chosen in a step, there must be another matching edge that conflicts with it and has an even earlier or equally good deadline. This allows the authors to prove that the heat of any unscheduled edge is bounded by a specific value.
Terminology
Summary
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
Problem Definition and Motivation
The Polyamorous Scheduling problem involves finding a periodic schedule of matchings in an edge-weighted graph to minimize the supremum heat over an infinite horizon The objective is to minimize heat(schedule) = sup e∈E, t≥0 he(t). A natural normalization sets the growth rate of the graph G to be G∗ = max v∈P Gv, and it is clear that OPT ≥ G∗ for all instances. p. 1 A natural normalization is that, given the growth rate of vertex v is
Gv =
X
e∋v
ge,
then we define the growth rate of the graph to be
G
∗ = max
v∈P
Gv. It is clear that
OPT ≥ G
∗
for all instances. We usually normalize G∗ = 1. The special case where G = (P, E) is a star is exactly the classical
bamboo garden trimming problem (BGT): each edge behaves like a bamboo
stalk growing at rate ge, and trimming it resets its height.Where the paper says it
Where the paper says it
Deadline-Driven Matching Algorithm
The Deadline-Driven Matching algorithm defines a deadline for an edge e with growth rate ge and current heat he(t) ≥ 1 as Dt(e) = t + 2 − he(t) / ge. The procedure for selecting the matching Mt on day t involves ordering eligible edges Et by non-decreasing deadline, breaking ties by a fixed arbitrary total order. p. 2 Form Mt by following the greedy procedure:
1. Order Et by non-decreasing deadline, breaking ties by a fixed arbitrary
total order on edges. Scan the edges in this order, adding e to Mt if and only if neither
endpoint of e is already incident to an edge in Mt. The resulting matching Mt is scheduled on day t; every edge e ∈ Mt
rests, so that
he(t + 1) = 0.Where the paper says it
Where the paper says it
Witness Lemma and Bounding Heat
The Witness Lemma proves that if an eligible edge e0 ∈ Et is not selected, there exists an edge f ∈ Mt with f ∩ e0 ≠ ∅ and Dt(f) < Dt(e0), or Dt(f) = Dt(e0) and f precedes e0 in the fixed arbitrary total order. This implies that for any day t, a witness edge wt can be fixed to bound e0’s heat. p. 2 If e0 is never selected up to some day T, then for every day t ≤ T on
which e0 is eligible but unscheduled, Lemma 1 supplies a witness edge. Since simultaneous blockers on the same day are redundant for the purpose of bounding e0’s heat, for any day t we will fix a witness edge wt
. Therefore,
X
f∈Fu
Nf ≤
2
ge
X
f∈Fu
gf ≤
2(1 − ge)
ge
,
and symmetrically for Fv. Thus, the total number of days me on which e is eligible but unscheduled
satisfies
me ≤
X
f∈Fu
Nf +
X
f∈Fv
Nf ≤
4(1 − ge)
ge
. Thus, the total number of days me on which e is eligible but unscheduled
satisfies
me ≤
X
f∈Fu
Nf +
X
f∈Fv
Nf ≤
4(1 − ge)
ge
. Since e accrues heat at rate ge, its heat is bounded by
geme ≤ ge ·
4(1 − ge)
ge
= 4(1 − ge) < 4.Where the paper says it
Where the paper says it
Where the paper says it
Approximation Ratio Improvement
The algorithm is inspired by the Deadline-Driven Heuristic which is optimal for Bamboo Garden Trimming (BGT). Biktairov et al. p. 1 The general graph version, OPS, is considerably harder because a day’s
schedule must be a matching rather than a single choice. Biktairov et al. (2024)’s main algorithm [1], Reduce-Fastest, instead orders edges by decreasing growth rate and greedily matches those whose heat exceeds a threshold
xG∗
. Setting
x = 2 +
2
√
5
5
gives a
3 + √
5
approximation ratio. 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 4G∗ algorithm for Polyamorous Scheduling, improving
the previously known bound of 3 + √
5 ≈ 5. (2024)’s main algorithm [1], Reduce-Fastest, instead orders edges by decreasing growth rate and greedily matches those whose heat exceeds a threshold
xG∗
. Setting
x = 2 +
2
√
5
5
gives a
3 + √
5
approximation ratio.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
Theorem 1 states that the deadline-ordered greedy maximal matching achieves heat strictly less than 4G∗. This demonstrates that the deadline-based idea can be imported into the OPS setting to yield a better bound. p. 1 Setting
x = 2 +
2
√
5
5
gives a
3 + √
5
approximation ratio. We try to import BGT’s deadline-based idea directly into the OPS setting and see if this yields a better bound. A Deadline-Driven Algorithm for Polyamorous
Scheduling
Arjun Maneesh Agarwal∗
September 9, 2026
Abstract
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. The deadline-ordered greedy maximal matching achieves heat
strictly less than 4G∗
. This problem was being considered for a problem set for the
Graduate Algorithms course I am a TA for.Where the paper says it
Where the paper says it
Where the paper says it
References
[1] Yuriy Biktairov, Leszek Gasieniec, Wanchote Po Jiamjitrak, Namrata, Benjamin Smith, and Sebastian Wild. Simple approximation algorithms for polyamorous scheduling. p. 5 References
[1] Yuriy Biktairov, Leszek Gasieniec, Wanchote Po Jiamjitrak, Namrata,
Benjamin Smith, and Sebastian Wild. Simple approximation algorithms
for polyamorous scheduling. Simple approximation algorithms
for polyamorous scheduling. arXiv preprint arXiv:2411.Where the paper says it
Where the paper says it
[2] Leszek Gasieniec, Benjamin Smith, and Sebastian Wild. Polyamorous scheduling. p. 0 A Deadline-Driven Algorithm for Polyamorous
Scheduling
Arjun Maneesh Agarwal∗
September 9, 2026
Abstract
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. Polyamorous
scheduling. arXiv preprint arXiv:2403.Where the paper says it
Where the paper says it
[3] John Kuszmaul. Bamboo trimming revisited: Simple algorithms can do well too. p. 5 [3] John Kuszmaul. Bamboo trimming revisited: Simple algorithms can do
well too. Bamboo trimming revisited: Simple algorithms can do
well too. In Proceedings of the 34th ACM Symposium on Parallelism in
Algorithms and Architectures, pages 411–417.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved scheduling for complex social group interactions by minimizing maximal weighted waiting time between consecutive occurrences of same relationships, as defined in Polyamorous Scheduling Problem. This enables AI systems to generate optimal periodic meeting schedules for individuals with multiple connections, ensuring no relationship experiences excessively long gaps between scheduled meetings.
-
Enhanced algorithmic efficiency by implementing the deadline-ordered greedy maximal matching strategy to solve the Polyamorous Scheduling Problem. This allows AI scheduling modules to quickly select feasible matchings on each day based on predicted heat accumulation, leading to faster and better solutions than previous methods like Reduce-Fastest.
-
More robust approximation guarantees for scheduling problems by utilizing the witness lemma derived from the deadline-driven matching algorithm. This provides a theoretical bound of strictly less than 4G star, which can be used to design AI systems that guarantee a schedule quality better than a simple 4G star approximation ratio for general graph instances.
Abstract
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 about 5.236. Our algorithm is inspired by the Deadline-Driven Heuristic which is optimal for Bamboo Garden Trimming (BGT).
Sources
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles