The Fair Periodic Assignment Problem

Bart van Rossum; Rolf van Lieshout

REVIEW 3 major objections 6 minor 11 references

The Fair Periodic Assignment Problem

T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A fair periodic schedule never needs more than one extra worker beyond the efficient minimum.

desk verdict Strong scheduling theory with a real but fillable gap: the price-of-fairness proof rests on an unproven phase-repetition step. read the letter →

arxiv 2507.04537 v1 pith:FQHUYH37 submitted 2025-07-06 cs.DS math.OC

Rolf van Lieshout , Bart van Rossum This is my paper · ORCID

classification cs.DSmath.OC

keywords periodicassignmentfairnesscyclicschedulingtravelingsalesmanproblemNearestNeighborheuristicpriceofidleintervalgraphsubtourpatching

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Work rosters that repeat weekly, such as train crew schedules, normally seek to minimize the number of workers. This paper adds a fairness requirement: every worker should perform the same sequence of tasks over time, so the assignment must be a single cycle through all tasks. The paper's central result is that this fairness condition can never force more than one additional worker beyond the efficient minimum, and that a fair schedule achieving this bound can be found with the Nearest Neighbor heuristic. The paper also gives a complete characterization of when fairness is free: a schedule exists using the minimum number of workers exactly when the graph of idle intervals is weakly connected, leading to an O(n log n) exact algorithm. Finally, it shows that allowing aperiodic or merely long-run-balanced schedules does not reduce the worker count below what fair periodic schedules already achieve.

What carries the argument

The central object is the idle interval graph. Idle intervals are maximal closed time intervals within the period where fewer than L tasks are active; each task has its start time in one idle interval and its end time in another, and the graph has a node per idle interval and an arc per task pointing from the interval of its start to the interval of its end. The paper proves that weak connectivity of this graph is the exact condition for the existence of a fair assignment with L workers. The algorithms then operate on transition arcs: Shift-Sort-and-Match builds an optimal PAP assignment by matching end times to start times after shifting the period so that I(0)=L, Nearest Neighbor constructs a Hamiltonian cycle by repeatedly visiting the task whose start is closest to the current task's end, and Patching eliminates subtours by swapping overlapping transition arcs that belong to different cycles without changing total transition time.

What would settle it

Enumerate all small instances of the periodic assignment problem with L = 2, say all sets of up to six tasks with integer start and end times, and check whether Nearest Neighbor ever returns a tour requiring 4 workers; a single such instance would disprove the price-of-fairness theorem. More directly, search for an instance in which some task begins after L full periods but the peak number of simultaneously active tasks never reaches L+1, since the proof of Theorem 5 requires that this cannot happen.

Watch

Extended reading notes

Core claim

The paper models a fair schedule as a Hamiltonian cycle in the transition graph: a fair periodic assignment is a single directed cycle covering all tasks, and the number of workers it uses equals the total task plus transition time divided by the period. The main discovery is that the price of fairness is at most one worker: Nearest Neighbor, which repeatedly moves to the closest unvisited task, always returns a fair assignment using at most L+1 workers, where L is the peak simultaneous load of the instance, and this bound is tight. The paper then characterizes the favorable case: an instance admits a fair assignment with exactly L workers if and only if the idle interval graph—the graph connecting maximal intervals of time in which fewer than L tasks are active—is weakly connected. Building on this, the Patching algorithm converts any efficient assignment into a fair one when possible and otherwise falls back on Nearest Neighbor, giving an O(n log n) exact algorithm for the Fair Periodic Assignment Problem. Section 4 extends the setup to aperiodic schedules and proves that any instance admitting a balanced assignment with q workers also admits a fair periodic assignment with q workers, so the price of fairness cannot be lowered by abandoning periodicity.

Load-bearing premise

The load-bearing premise is the argument that whenever Nearest Neighbor starts a task after L full periods, some earlier moment must have L+1 tasks active at once; the paper asserts this step rather than deriving it, and the at-most-one-extra-worker bound collapses if it fails.

Editorial extensions

If this is right

Every instance of the periodic assignment problem has a fair periodic schedule with at most L+1 workers; fairness never costs more than one additional employee.
The price of fairness is exactly 1/L, and this bound is tight: some instances require L+1 workers for any fair schedule.
An efficient solution can be made fair without adding workers whenever the idle interval graph is weakly connected; the Patching algorithm returns the fair solution in O(n log n) time.
If the idle interval graph is not weakly connected, the Patching algorithm falls back on Nearest Neighbor and still returns an optimal fair assignment with L+1 workers in O(n log n) time.
Aperiodic schedules and long-run-balanced assignments buy nothing in worker count: balanced assignments with q workers exist exactly when fair periodic assignments with q workers exist.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Going beyond the paper, the idle-interval-graph characterization gives a quick structural test for whether fairness is free: a planner only needs to compute maximal low-load intervals and check connectivity, without first constructing a fair tour.
Going beyond the paper, the Nearest Neighbor bound suggests that the transition graph's interval structure is what tames greedy TSP; similar one-worker guarantees may hold for other greedy rules on periodic interval instances, though the paper does not explore this.
Going beyond the paper, the equivalence between balanced and fair schedules means the practical value of the fairness notion lies mainly in the exact rotation pattern, rather than in worker count, since fairness is almost free in efficiency terms.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Rolf, you should read this one. It introduces the Fair Periodic Assignment Problem, proves that the price of fairness is at most one extra worker, gives an O(n log n) exact algorithm for the fair case, and shows that aperiodic balanced schedules don't help. The idle-interval graph characterization is clean, and the O(n log n) PAP algorithm is a solid improvement over the previous O(n^2 log n). The paper is worth serious referee time.

The good stuff first. Theorem 3's characterization of optimal PAP solutions is sound, and Shift-Sort-and-Match is a neat, correct algorithm. The idle-interval graph and Lemma 10/Theorem 11 are the real heart: an instance admits an efficient fair solution iff its idle interval graph is weakly connected. The patching algorithm on top of that is plausible and the runtime bound is right. Section 4's equivalence between balanced aperiodic assignments and fair periodic ones is a nice capstone, though it's only sketched.

Now the soft spot, and it's the one the stress-test note nails: Theorem 5's proof is three sentences. The step from 'the NN tour uses more than L+1 workers' to 'some task starts after L periods' is fine (a simple counting argument). But the next step—'in the first L periods, a task is performed at time a' and therefore 'I(a+ε)=L+1'—is not derived. The instants a+pT could fall inside transition arcs, which contribute to M(t), not I(t). The proof never bounds M(t) at those instants, so the contradiction doesn't follow as written. Since Corollary 6 and the fallback branch of Algorithm 3 both depend on Theorem 5, this gap is load-bearing. I couldn't find a counterexample, and the claim may well be true, but the argument is incomplete.

Minor things: the proof of Theorem 16 is also a sketch, and the uncrossing in Theorem 3 (i)⇒(iv) is written too quickly. These are fixable with expanded writeups.

Bottom line: the structural results and algorithms are the main contribution, and they look correct. The price-of-fairness theorem is the headline, and it needs a real proof. Send it to review, but make sure the referee pushes for a complete proof of Theorem 5 before accepting.

Referee Report

3 major / 6 minor

Summary. The paper studies the Periodic Assignment Problem (PAP) and its fair variant (FPAP), in which a set of T-periodic tasks must be covered by a single Hamiltonian cycle so that all workers perform the same task sequence. The authors propose Shift-Sort-and-Match, an O(n log n) exact algorithm for PAP; prove that the Nearest Neighbor heuristic returns a fair assignment with at most L+1 workers, giving a price of fairness of 1/L; characterize instances admitting fair and efficient assignments via weak connectivity of an idle-interval graph; and present Patching, an O(n log n) exact algorithm for FPAP. They also argue that allowing aperiodic or balanced assignments does not reduce the required number of workers.

Significance. If the results are correct, this is a clean and appealing contribution to cyclic scheduling: a tight one-extra-worker price of fairness, a characterization of fair-efficient instances, and near-linear exact algorithms. The paper is theoretical and contains no fitted parameters; the main tools are classical (Dilworth, interval graph coloring, TSP heuristics) and the structural lemmas are stated in a falsifiable way. The computational claims are strong and would be of interest to the ATMOS/cyclic-scheduling community. However, the proof of the headline Nearest Neighbor bound is incomplete, and the Patching algorithm's cycle-index update is underspecified, so the results are not yet established as written.

major comments (3)

[Section 3.1, Theorem 5 proof] Section 3.1, proof of Theorem 5: the step "If the assignment requires more than L+1 workers, there is some task i=(a,b) that is started after L periods... This means that in the first L periods, a task is performed at time a" is not justified. The first implication can be derived from the fact that the last task plus the final transition last less than 2T, but the second is exactly the load argument that is missing: the Nearest Neighbor path is not T-periodic, so a start at unrolled time a+qT with q>=L does not imply task starts at the same phase a in each of the first L periods, and at the instants a+rT+epsilon the worker may be in a transition rather than inside a task. Consequently I(a+epsilon)=L+1 is not established. Since Corollary 6 and the fallback branch of Algorithm 3 both depend on this bound, the proof must be completed.
[Section 3.3, Algorithm 3 and Theorem 12] Section 3.3, Algorithm 3 and Theorem 12: the claim that "the cycle indices can be updated in constant time after each patching operation" is not supported. Line 13 updates only V[U[k]] and V[U[l]], but after previous patches the current cycle containing task k (or l) may consist of many original cycles; those other entries of V remain stale, so the same-cycle test on line 11 can return the wrong answer. The "dedicated two-array data structure" is not described, and no amortized analysis is given. The O(n log n) complexity claim for Patching therefore needs either a detailed data structure with an amortized bound or a revision of the algorithm.
[Section 3.2, Lemma 10] Section 3.2, Lemma 10: in the second case of the overlap argument, the statement "If t2 > t1, no transition arcs are active in the interval (t1,t2)" ignores the possibility that C1 itself has a later block of transition arcs in the same idle interval starting before t2. The intended contradiction can likely be repaired by considering the first gap in coverage of the idle interval, but as written the proof is incomplete. Since Lemma 10 underpins Theorem 11, this should be fixed.

minor comments (6)

[Section 2.1, Theorem 3 proof] In part (i)->(iv), the "without loss of generality" ordering "b1 < am < b2 < a1 < ... < bm < a_{m-1}" is not derived and appears inconsistent; please rewrite the uncrossing argument with a clear cyclic ordering.
[Figures 3 and surrounding text] The spellings "Nearest Neighor" and "univisited" should be corrected to "Nearest Neighbor" and "unvisited".
[Sections 3.2 and 3.1] The text refers to "Theorem 6" when the price-of-fairness statement is Corollary 6, and Lemma 8 refers to "Theorem 7" instead of Definition 7.
[Section 2.1 and Theorem 12 proof] There are typos "where the where" and "ON (n)" that should be fixed.
[Corollary 6] The term "price of fairness" is used both for the absolute one-extra-worker bound and for the relative increase 1/L; please define which quantity is meant.
[Section 4, Observation 15] "Hr is weakly connected if and only H is connected" should read "if and only if H is connected".

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The results are derived from definitions; the only external inputs are classical background (Dilworth's theorem, interval graph coloring, prior PAP work) and the balanced-assignment definitions of [4],[5]. There are no fitted constants and no invented physical entities.

assumptions (4)

standard math L workers always suffice for the Periodic Assignment Problem and the optimum uses exactly L workers.
Used in Section 1.2 and Theorem 3 as the lower bound and baseline for the price of fairness; follows from Dilworth's theorem and periodic posets of [9],[10].
domain assumption Workers are identical and any rest time can be absorbed into task durations, so only start and end times matter.
Stated in Section 1.1; this makes the transition graph complete and the fair variant a TSP.
domain assumption Fairness is defined as a single Hamiltonian cycle, meaning all workers execute the same task sequence.
Definition 2; this is the paper's chosen fairness notion and drives all results.
domain assumption The balanced assignment framework of [4],[5] applies and its connection to the rolled-out idle interval graph is as asserted.
Section 4 uses this without a fully self-contained proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Fair Periodic Assignment Problem." pith.science (2026). https://pith.science/paper/FQHUYH37

@misc{pith2026250704537,
  author       = {Pith},
  title        = {Pith review of: The Fair Periodic Assignment Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FQHUYH37}},
  note         = {Machine review of arXiv:2507.04537}
}

read the original abstract

We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a O(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a O(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.

Figures

Figures reproduced from arXiv: 2507.04537 by the authors.

**Figure 1.** shows a PAP instance, together with three possible representations of an efficient solution that requires the minimum of two workers. In Figure 1a, the tasks to be performed periodically are labeled I1, . . . , I4 and displayed as circular arcs. Dotted arcs indicate the transition arcs in the efficient solution, requiring two workers to operate two disjoint schedules of two tasks each. Figure 1b represents the same … view at source ↗

**Figure 2.** displays three representations of a fair solution to a FPAP instance featuring the same set of tasks as [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Nearest Neighbor solution versus optimal solution. Theorem 5. The Nearest Neighbor algorithm returns a fair periodic assignment requiring at most L + 1 workers in O(n log n) time. Proof. We first analyze the runtime. A crucial observation is that the distance of the current task to the next depends solely on the end time of the current task and start time of the next task. If unvisited tasks are stored in increasing… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Two instances of the periodic assignment problem. Instance A does not admit a fair and efficient solution, while instance B does. Throughout, we illustrate our analysis on the instances in [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

**Figure 5.** Figure 5: Idle time function and idle interval graph of instance A and B. Our goal is to study how the connectivity of idle intervals determines the number of disjoint cycles in a periodic assignment. To this end, we introduce the idle interval graph, representing how the variou…

**Figure 6.** Figure 6: Rolled-out idle interval graph of instance B, showing the first three periods. There is a many-to-one mapping from nodes and arcs in the rolled-out graph to nodes and arcs in the periodic graph. This results in the following observation: Observation 15. Hr is weakly co…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 9 canonical work pages

[1]

Peri- odic Event Scheduling with Flexible Infrastructure Assignment

Enrico Bortoletto, Rolf N van Lieshout, Berenike Masing, and Niels Lindner. Peri- odic Event Scheduling with Flexible Infrastructure Assignment. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Sys- tems (ATMOS 2024) , volume 123 of Open Access Series in Informatics (OASIcs) , pages 4:1–4:18, Dagstuhl, Germany, 2...

doi:10.4230/oasics.atmos.2024.4 2024
[2]

Is equality always desir- able? Analyzing the trade-off between fairness and attractiveness in crew rostering

Thomas Breugem, Twan Dollevoet, and Dennis Huisman. Is equality always desir- able? Analyzing the trade-off between fairness and attractiveness in crew rostering. Management Science, 68(4):2619–2641, 2022. doi:10.1287/mnsc.2021.4005

work page arXiv 2022
[3]

Well-solvable special cases of the traveling salesman problem: A survey

Rainer E Burkard, Vladimir G Deineko, Rene Van Dal, Jack AA van der Veen, and Gerhard J Woeginger. Well-solvable special cases of the traveling salesman problem: A survey. SIAM Review, 40(3):496–546, 1998

work page 1998
[4]

Balanced Assignments of Periodic Tasks

H´ elo ¨ ıse Gachet and Fr´ ed´ eric Meunier. Balanced Assignments of Periodic Tasks. In Paul C. Bouman and Spyros C. Kontogiannis, editors, 24th Symposium on Algo- rithmic Approaches for Transportation Modelling, Optimization, and Systems (AT- MOS 2024) , volume 123 of Open Access Series in Informatics (OASIcs) , pages 5:1– 5:12, Dagstuhl, Germany, 2024....

work page doi:10.4230/oasics.atmos.2024.5 2024
[5]

Balanced assignments of periodic tasks

H´ elo ¨ ıse Gachet and Fr´ ed´ eric Meunier. Balanced assignments of periodic tasks. 2025. arXiv:2407.05485. 19

work page Pith review arXiv 2025
[6]

An optimal solution for the channel-assignment problem

Gupta, Lee, and Leung. An optimal solution for the channel-assignment problem. IEEE Transactions on Computers, C-28(11):807–810, 1979. doi:10.1109/TC.1979. 1675260

work page doi:10.1109/tc.1979 1979
[7]

Jan H. M. Korst, Emile H. L. Aarts, Jan Karel Lenstra, and Jaap Wessels. Periodic assignment and graph colouring. Discrete Applied Mathematics, 51(3):291–305, 1994. doi:10.1016/0166-218X(92)00036-L

work page doi:10.1016/0166-218x(92)00036-l 1994
[8]

Eugene Levner, Vladimir Kats, David Alcaide L´ opez de Pablo, and T.C.E. Cheng. Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & Industrial Engineering, 59(2):352–361, 2010. doi:10.1016/j.cie.2010.03.013

work page doi:10.1016/j.cie.2010.03.013 2010

Show all 11 references

[9]

Minimizing the number of vehicles to meet a fixed periodic schedule: An application of periodic posets

James B Orlin. Minimizing the number of vehicles to meet a fixed periodic schedule: An application of periodic posets. Operations Research, 30(4):760–776, 1982

1982
[10]

Integrated periodic timetabling and vehicle circulation schedul- ing

Rolf N van Lieshout. Integrated periodic timetabling and vehicle circulation schedul- ing. Transportation Science, 55(3):768–790, 2021. doi:10.1287/trsc.2020.1024

2021
[11]

Cyclic and non-cyclic crew rostering problems in public bus transit

Lin Xie and Leena Suhl. Cyclic and non-cyclic crew rostering problems in public bus transit. OR Spectrum, 37:99–136, 2015. doi:10.1007/s00291-014-0364-9 . 20

2015 doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Peri- odic Event Scheduling with Flexible Infrastructure Assignment

Enrico Bortoletto, Rolf N van Lieshout, Berenike Masing, and Niels Lindner. Peri- odic Event Scheduling with Flexible Infrastructure Assignment. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Sys- tems (ATMOS 2024) , volume 123 of Open Access Series in Informatics (OASIcs) , pages 4:1–4:18, Dagstuhl, Germany, 2...

doi:10.4230/oasics.atmos.2024.4 2024

[2] [2]

Is equality always desir- able? Analyzing the trade-off between fairness and attractiveness in crew rostering

Thomas Breugem, Twan Dollevoet, and Dennis Huisman. Is equality always desir- able? Analyzing the trade-off between fairness and attractiveness in crew rostering. Management Science, 68(4):2619–2641, 2022. doi:10.1287/mnsc.2021.4005

work page arXiv 2022

[3] [3]

Well-solvable special cases of the traveling salesman problem: A survey

Rainer E Burkard, Vladimir G Deineko, Rene Van Dal, Jack AA van der Veen, and Gerhard J Woeginger. Well-solvable special cases of the traveling salesman problem: A survey. SIAM Review, 40(3):496–546, 1998

work page 1998

[4] [4]

Balanced Assignments of Periodic Tasks

H´ elo ¨ ıse Gachet and Fr´ ed´ eric Meunier. Balanced Assignments of Periodic Tasks. In Paul C. Bouman and Spyros C. Kontogiannis, editors, 24th Symposium on Algo- rithmic Approaches for Transportation Modelling, Optimization, and Systems (AT- MOS 2024) , volume 123 of Open Access Series in Informatics (OASIcs) , pages 5:1– 5:12, Dagstuhl, Germany, 2024....

work page doi:10.4230/oasics.atmos.2024.5 2024

[5] [5]

Balanced assignments of periodic tasks

H´ elo ¨ ıse Gachet and Fr´ ed´ eric Meunier. Balanced assignments of periodic tasks. 2025. arXiv:2407.05485. 19

work page Pith review arXiv 2025

[6] [6]

An optimal solution for the channel-assignment problem

Gupta, Lee, and Leung. An optimal solution for the channel-assignment problem. IEEE Transactions on Computers, C-28(11):807–810, 1979. doi:10.1109/TC.1979. 1675260

work page doi:10.1109/tc.1979 1979

[7] [7]

Jan H. M. Korst, Emile H. L. Aarts, Jan Karel Lenstra, and Jaap Wessels. Periodic assignment and graph colouring. Discrete Applied Mathematics, 51(3):291–305, 1994. doi:10.1016/0166-218X(92)00036-L

work page doi:10.1016/0166-218x(92)00036-l 1994

[8] [8]

Eugene Levner, Vladimir Kats, David Alcaide L´ opez de Pablo, and T.C.E. Cheng. Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & Industrial Engineering, 59(2):352–361, 2010. doi:10.1016/j.cie.2010.03.013

work page doi:10.1016/j.cie.2010.03.013 2010