A Deadline-Driven Algorithm for Polyamorous Scheduling

arXiv:2609.10641 · cs.DS · Submitted 2026-09-09 · Read on arXiv

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

Where the paper says it

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.

The special case where G = (P, E) is a star is exactly the classical bamboo garden trimming problem (BGT). p. 1
Where the paper says it

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.

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

Where the paper says it

Form Mt by following the greedy procedure: 1. Order Et by non-decreasing deadline, breaking ties by a fixed arbitrary total order on edges.

The resulting matching Mt is scheduled on day t, and every edge e ∈ Mt rests so that he(t + 1) = 0. p. 2
Where the paper says it

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.

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

Where the paper says it

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 .

The analysis shows that the total number of days me on which e is eligible but unscheduled satisfies me ≤ 4(1 − ge). p. 4
Where the paper says it

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 .

This leads to the conclusion that e accrues heat bounded by geme ≤ ge · 4(1 − ge) = 4(1 − ge). p. 4
Where the paper says it

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.

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

Where the paper says it

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.

’s main algorithm, Reduce-Fastest, sets x = 2 + 2/√5/5 to give a 3 + √5 approximation ratio. p. 1
Where the paper says it

(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.

The authors present a 4G∗ algorithm for Polyamorous Scheduling, improving the previously known bound of 3 + √5 ≈ 5. p. 0
Where the paper says it

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.

236. This result is achieved by setting x = 2 + √5/5. p. 1
Where the paper says it

(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.

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

Where the paper says it

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.

The work is inspired by prior research on BGT and aims to find schedules of pairwise meetings in a complex social group. p. 0
Where the paper says it

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 paper was considered for a problem set for the Graduate Algorithms course. p. 4
Where the paper says it

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.

References

[1] Yuriy Biktairov, Leszek Gasieniec, Wanchote Po Jiamjitrak, Namrata, Benjamin Smith, and Sebastian Wild. Simple approximation algorithms for polyamorous scheduling. p. 5

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.

arXiv preprint arXiv:2411. p. 5
Where the paper says it

Simple approximation algorithms for polyamorous scheduling. arXiv preprint arXiv:2411.

06292, November 2024

[2] Leszek Gasieniec, Benjamin Smith, and Sebastian Wild. Polyamorous scheduling. p. 0

Where the paper says it

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.

arXiv preprint arXiv:2403. p. 5
Where the paper says it

Polyamorous scheduling. arXiv preprint arXiv:2403.

00465, March 2024

[3] John Kuszmaul. Bamboo trimming revisited: Simple algorithms can do well too. p. 5

Where the paper says it

[3] John Kuszmaul. 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. p. 5
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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