{"id":"d2d4d215-290d-47f5-a707-13dff431ecfa","arxiv_id":"2507.04537","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In periodic task scheduling, requiring every worker to follow the same sequence adds at most one extra worker, and an optimal fair sequence can be found in O(n log n) time.","lead":"The authors study how to schedule repeating tasks among workers, first to minimize the number of workers and then under a fairness rule that all workers rotate through the same task sequence. They show that this fairness rule costs at most one extra worker and give fast O(n log n) algorithms for both the efficient and the fair versions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The load-bearing gap is Theorem 5's phase-repetition step: the proof does not establish that an NN tour with more than L+1 workers forces a point with I(t)=L+1, because transition-active instants are not ruled out; Corollary 6 and Algorithm 3's fallback both depend on this step.","rationale":"The reader's weakest assumption identifies exactly the step I would stress-test: the phase-repetition inference in Theorem 5. I reviewed the other main components: the idle-interval characterization in Theorems 10 and 11 appears internally coherent, and the Patching algorithm's arc-overlap invariant is plausible; no counterexample to the one-extra-worker bound emerged in manual construction. The proof of Theorem 5, however, leaves unstated why the NN path must be inside a task at each of the first L occurrences of the relevant start residue, rather than inside a transition. This matters because Theorem 5 is the source of the price-of-fairness result and of the fallback in Algorithm 3. The appropriate disposition remains conditional acceptance with a request to expand that proof; my read does not move the verdict, so it stays unchanged.","tokens_in":12044,"tokens_out":39860,"duration_ms":423346,"concrete_test":"Run an exhaustive check on a discrete circle: fix T=12, n<=7, all start and end times on the grid {0,...,11}, each task duration at least one grid step, and for every instance compute the NN cycle worker count q and the maximum load L. If any instance has q>L+1, Theorem 5 and Corollary 6 are false. For each instance with q>L+1, also inspect the unrolled NN path at the instants a, a+T, ..., a+(L-1)T, where a is the start residue of the last-started task, and record whether the path is in a task or a transition. Any transition-active instant directly invalidates the proof's phase-repetition step. If no violations appear at this scale, the bound gains support but the missing lemma should still be written out before acceptance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive step of Theorem 5 is the paragraph in Section 3.1 asserting that if the Nearest Neighbor cycle uses more than L+1 workers, then some task i=(a,b) starts after L complete periods, and that this implies a task is performed at time a in each of the first L periods, forcing I(a+epsilon)=L+1. The first implication can be justified from unrolled start times: if every task started before LT, the total cycle length would be at most (L+1)T. The second implication is not derived. Along the one-worker unrolled NN path, the instants a, a+T, ..., a+(L-1)T could fall inside transition arcs rather than inside tasks; the proof never bounds M(t) at those instants. A transition-active crossing contributes to M, not I, and does not contradict I(t)<=L. Since Theorem 5 underpins Corollary 6 (price of fairness 1/L) and is the fallback branch of Algorithm 3, this gap is load-bearing. I found no counterexample, and the guarantee may be true, but the argument as written is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12303,"tokens_out":19740,"duration_ms":222186,"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":[{"comment":"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":"Section 3.1, Theorem 5 proof"},{"comment":"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":"Section 3.3, Algorithm 3 and Theorem 12"},{"comment":"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.","section":"Section 3.2, Lemma 10"}],"minor_comments":[{"comment":"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.","section":"Section 2.1, Theorem 3 proof"},{"comment":"The spellings \"Nearest Neighor\" and \"univisited\" should be corrected to \"Nearest Neighbor\" and \"unvisited\".","section":"Figures 3 and surrounding text"},{"comment":"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":"Sections 3.2 and 3.1"},{"comment":"There are typos \"where the where\" and \"ON (n)\" that should be fixed.","section":"Section 2.1 and Theorem 12 proof"},{"comment":"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":"Corollary 6"},{"comment":"\"Hr is weakly connected if and only H is connected\" should read \"if and only if H is connected\".","section":"Section 4, Observation 15"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is Theorem 5; if a complete proof can be supplied, the paper would be a strong fit. I also recommend asking for a precise description of the cycle-index data structure in Algorithm 3, because the current pseudocode appears to under-specify the constant-time update."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nNow 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.\n\nMinor 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.\n\nBottom 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.","headline":"Strong scheduling theory with a real but fillable gap: the price-of-fairness proof rests on an unproven phase-repetition step.","tokens_in":12823,"tokens_out":16253,"would_cite":true,"duration_ms":175049,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A fair periodic schedule never needs more than one extra worker beyond the efficient minimum.","keywords":["periodic assignment","fairness","cyclic scheduling","traveling salesman problem","Nearest Neighbor heuristic","price of fairness","idle interval graph","subtour patching"],"falsifier":"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.","tokens_in":11856,"feed_emoji":"👷","tokens_out":7607,"duration_ms":82897,"temperature":0.7,"pith_summary":"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.","feed_headline":"Fair periodic schedules cost at most one extra worker","feed_subtitle":"All workers rotate through the same tasks, and efficiency drops by at most one employee.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the previous O(n^2 log n) PAP algorithm that Shift-Sort-and-Match improves on, along with the integrated timetabling context.","marker":"[10]"},{"why":"Establishes via periodic posets that L workers always suffice for PAP, the lower bound that the fairness analysis builds on.","marker":"[9]"},{"why":"Shows the special case with an idle instant reduces PAP to interval graph coloring and admits an L-worker assignment, a baseline the paper extends.","marker":"[7]"},{"why":"Provides the O(n log n) interval graph coloring algorithm used in that special case and a benchmark for the new runtime.","marker":"[6]"},{"why":"Direct inspiration, defining balanced (asymptotically fair) assignments of periodic tasks; Section 4 compares against this notion.","marker":"[4]"},{"why":"Extension of the balanced-assignment construction to linear period, used as the comparison point for aperiodic schedules.","marker":"[5]"}],"fun_headline_variants":["Fair periodic schedules: at most one extra worker","Price of fairness in scheduling is one worker max","Nearest neighbor yields fair rotation with one extra worker","One worker extra: guarantee for fair periodic assignment"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fair periodic schedules: at most one extra worker","Price of fairness in scheduling is one worker max","Nearest neighbor yields fair rotation with one extra worker","One worker extra: guarantee for fair periodic assignment"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000306,"raw_usage":{"total_tokens":1735,"prompt_tokens":911,"completion_tokens":824,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":764}},"tokens_in":527,"tokens_out":824,"duration_ms":8310,"temperature":1.0,"reasoning_tokens":764,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:49:12.445452+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Minimizing the number of vehicles to meet a fixed periodic schedule: An application of periodic posets","cited_arxiv_id":null,"evidence_quote":"Establishes via periodic posets that L workers always suffice for PAP, the lower bound that the fairness analysis builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows the special case with an idle instant reduces PAP to interval graph coloring and admits an L-worker assignment, a baseline the paper extends."},{"cited_title":"An optimal solution for the channel-assignment problem","cited_arxiv_id":null,"evidence_quote":"Provides the O(n log n) interval graph coloring algorithm used in that special case and a benchmark for the new runtime."},{"cited_title":"Balanced Assignments of Periodic Tasks","cited_arxiv_id":null,"evidence_quote":"Direct inspiration, defining balanced (asymptotically fair) assignments of periodic tasks; Section 4 compares against this notion."},{"cited_title":"Balanced assignments of periodic tasks","cited_arxiv_id":"2407.05485","evidence_quote":"Extension of the balanced-assignment construction to linear period, used as the comparison point for aperiodic schedules."}],"review_version":1}