A Simpler Analysis for ε \varepsilon -Clairvoyant Flow Time Scheduling

Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai · 2026

Read A Simpler Analysis for ε \varepsilon -Clairvoyant Flow Time Scheduling by Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17542.txt.

Introduction

Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai simplify a scheduling optimality proof. The setting is epsilon-clairvoyant flow time scheduling, where job sizes are known only roughly in advance. Flow time counts how long each job spends in the system overall. The algorithm under study is Shortest Lower-Bound First, from their earlier work. Their new analysis proves its optimality with a cleaner argument. The result tightens theory for scheduling under partial foresight.

Catalog record

CREATORAnupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40203
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.17542

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Simpler Analysis for ε \varepsilon -Clairvoyant Flow Time Scheduling Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai Abstract We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS’25], for minimizing the total flow time in the ε \varepsilon -clairvoyant setting. \typearea 14 1 Introduction We consider the classical problem of minimizing the total flow time in the online setting where jobs arrive over time and preemption is allowed. The flow time of a job is the total time that a job spends in the system. We study the objective of minimizing the total flow time of all the jobs on a single machine. In [ Gup+25 ] , the authors of the present paper studied this problem in the \varepsilon -clairvoyant setting, which is defined as follows. When a job j arrives, we know nothing about its processing time p_{j} . However, the value p_{j} is revealed when an \varepsilon -fraction of job j remains to be processed, for a constant \varepsilon\in[0,1] . They showed that a natural algorithm, called Shortest Lower-Bound First (SLF), achieves a competitive ratio of at most \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil} when \varepsilon>0 , and this bound is best possible for deterministic algorithms. In this technical note, we present a simplified analysis of SLF, which yields the same tight bound on the competitive ratio. For the remaining aspects of this model and its connection to related work, we refer to [ Gup+25 ] . In the remainder of this note, we first present the SLF algorithm and then prove the following theorem. Theorem 1.1 ( [ Gup+25 ] ) . For any constant \varepsilon\in(0,1] , there is a deterministic \varepsilon -clairvoyant algorithm SLF that is \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil} -competitive for the objective of minimizing the total flow time on a single machine. 1.1 Technical Overview We prove that SLF is locally \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil} -competitive at any time t , meaning that there are at most \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil} times as many jobs active in the algorithm’s schedule as in an optimal schedule. This is a necessary property for constant competitive algorithms for this problem, and we also use it in [ Gup+25 ] . However, there are two major places in which we improve our analysis in [ Gup+25 ] , which we explain in the following two paragraphs. Frozen Jobs instead of Early Arrivals. A key ingredient in the analysis of [ Gup+25 ] is the Early Arrival Lemma, which shows that we can make certain jobs arrive earlier without affecting the set of active jobs at time t or their elapsed times in the algorithm’s schedule. Clearly, such a modification can only help an optimal solution to reduce its number of active jobs at some target time t , hence never improves the local competitive ratio. In [ Gup+25 ] , we iteratively search for what we called magical times s with the property that during [s,t] the algorithm does not work on jobs j\in J_{s} whose remaining time is more than \varepsilon p_{j} at time s ( p_{j} is the total length of job j ). Then, we move the arrival time of jobs that arrive after time s to arrive earlier at time s . This modification can only help an optimal solution to reduce its load at time t and adds structure to the schedule produced by our algorithm from time s onwards, which greatly helps in the analysis. In the analysis presented here, we completely avoid this technical reduction. Instead, we mark such jobs J_{s} as frozen as soon as the algorithm no longer works on them, before time t . This is possible due to a more powerful Fast Forward Lemma (cf. Lemma 3.6 ), which does not require all jobs to arrive at the beginning of the fast-forward interval, but instead allows jobs to arrive over time until the next job becomes frozen or all jobs are known. Fixed-Length Prefix Bounds instead of Valid Assignments. The second major change is that we use a weaker invariant over time. In [ Gup+25 ] , we inductively show for any time t a fractional assignment between the active jobs in the algorithm’s schedule and the active jobs in the optimal schedule. The value of a node corresponding to job j , in this fractional matching, is its remaining processing time at time t in the algorithm’s schedule or the optimal schedule, respectively (we call this the job’s volume at time t ). Specifically, we show that at any time there exists an assignment that is at most \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil} -expanding. 1 1 1 This means that any prefix of length x of SLF’s queue sorted in nonincreasing order of remaining time is assigned to at most \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil}\cdot x jobs of \mathrm{OPT} . This allows us to bound the number of active jobs in the algorithm’s schedule with \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil} times the number of active jobs in the optimal schedule, thus proving Theorem 1.1 . This invariant has also been used in Schrage’s original proof of SRPT’s optimality for minimizing total flow time [ Sch68 ] . We use a simpler invariant instead. As in [ Gup+25 ] we fix a time t for which we want to prove local competitiveness, and then only show an invariant (that depends on t ) over all times t^{\prime}\leq t . But instead of requiring a bounded expansion for all prefixes of active jobs in the optimal solution, ordered by decreasing volume as in [ Gup+25 ] , we only require that the total volume of the \smash{\left\lceil\nicefrac{{1}}{{\varepsilon}}\right\rceil}\cdot|\mathrm{OPT}(t^{\prime},t)| jobs with largest volume in the algorithm’s queue is at least as much as the total volume of the jobs in \mathrm{OPT}(t^{\prime},t) in OPT’s queue. Here, \mathrm{OPT}(t^{\prime},t) denotes the set of jobs that are active in the optimal schedule at time t^{\prime} and time t . This significantly simplifies the proof, as we do not need to maintain a full fractional assignment of bounded expansion over time, but only need to argue about the volume of a single set of jobs . This technique has previously been used in the context of online flow time scheduling [ BD07 , AT18 , ALT21 ] . A major challenge is that our SLF algorithm may process multiple jobs at the same time (using Round-Robin on a certain subset of jobs) and hence reduce the volume of multiple jobs at the same time. This is a crucial difference compared to those earlier works, in which an algorithm works at any time on at most one job, and thus, makes inductive arguments about volume changes much easier to handle. 2 The Shortest-Lower-Bound-First Algorithm We first restate the Shortest Lower-Bound First ( \mathrm{SLF} ) algorithm, which was introduced in [ Gup+25 ] . For any time t , let {\mathrm{SLF}}(t) denote the set of active (released and unfinished) jobs in the schedule of {\mathrm{SLF}} . We further distinguish between known and unknown jobs. Definition 2.1 (Known/Unknown Jobs) . Let j be an active job in {\mathrm{SLF}} at time t . We say that a job j is known if r_{j}(t)\leq\varepsilon\cdot p_{j} . Otherwise, j is unknown . Let U(t) and K(t) denote the unknown and

Read the complete text