text:
\section{Algorithms}\label{sec_alg}

\textsc{Lax}\xspace~ maintains $m$ stacks of jobs (first-in-last-out data structures) $H_1, \dots, H_m$, each corresponding to one machine. Then we always run the top job of stack $i$ on machine $i$. We define the \emph{frontier} $F$ to be the set consisting of the top job of each stack (i.e. all currently running jobs.) Initially at time zero, all stacks are empty.

To complete the description of \textsc{Lax}\xspace, it remains to define how the $H_i$'s are updated. To do so, we need some definitions.

\begin{definition}[Strictly Feasible Jobs]\label{def_strict_feasible}
    Let $\alpha \geq 1$ be a sufficiently large constant (chosen later.) A job $j$ is strictly feasible at time $t$ (with respect to \textsc{Lax}\xspace) if:
    \begin{enumerate}
        \item It still has half of its laxity remaining, so $\ell_j(t) \geq \frac{1}{2} \ell_j$,
        \item and there exists a job $j'$ on the frontier such that $\alpha x_j \leq \ell_{j'}$.
    \end{enumerate}
\end{definition}

Note that the first condition of strict feasibility implies feasibility (with some extra slack), and the latter says that if we pre-empt such a $j'$ by $j$, then we can still potentially complete both $j'$ and $j$. \textsc{Lax}\xspace~ will only consider pushing strictly feasible jobs onto the stacks (i.e. pre-empt a job on the frontier.) Further, for technical reasons, \textsc{Lax}\xspace~ will only consider jobs that it is \emph{responsible for}:

\begin{definition}[\textsc{Lax}\xspace/\textsc{SRPT}\xspace-Responsible Jobs and Pseudo-Release Times]\label{def_lax_response}
    We say \textsc{Lax}\xspace~ is responsible for job $j$ (or job $j$ is \textsc{Lax}\xspace-responsible) if there exists a time $t \in [r_j, r_j + \frac{\ell_j}{2}]$ such that at this time, there exist at least $\frac{m}{2}$ jobs $j'$ on the frontier satisfying $\alpha x_{j'} \geq \ell_j$. Further, we define $j$'s pseudo-release time $\tilde{r}_j$ to be the earliest such time $t \in [r_j, r_j + \frac{\ell_j}{2}]$. If no such $t$ exists, then \textsc{SRPT}\xspace~ is responsible for $j$.
\end{definition}

Roughly, \textsc{Lax}\xspace~ and \textsc{SRPT}\xspace~ will both perform well on the jobs that they are responsible for. Now we are ready to define how to update the $H_i$'s. There are two types of events that cause \textsc{Lax}\xspace~ to update the $H_i$'s: reaching a job's pseudo-release time or completing a job.

When we reach job $j$'s pseudo-release time, so $j$ is \textsc{Lax}\xspace-responsible and $t = \tilde{r}_j$ (note $\tilde{r}_j$ can be determined online by \textsc{Lax}\xspace), we do the following:
\begin{enumerate}[a)]
    \item If $j$ is strictly feasible, then \emph{push} $j$ onto some stack whose top job $j'$ satisfies $\alpha x_j \leq \ell_{j'}$.
    \item Else if there exists a stack whose top job $j'$ satisfies $\ell_j > \ell_{j'}$ and whose second-top job $j''$ satisfies $\alpha x_j \leq \ell_{j''}$, then \emph{replace} the top job $j'$ by $j$.
\end{enumerate}

When we complete a job $j$ that was on top of stack $H_i$, we do the following:
\begin{enumerate}[a)]
    \item \emph{Pop} $j$ off of stack $H_i$.
    \item Keep \emph{popping} $H_i$ until the top job of $H_i$ is feasible.
\end{enumerate}

This completes the description of \textsc{Lax}\xspace.

\section{Putting it all together}\label{sec_final}

In this section, we prove our main result, \Cref{thm_main_deterministic}, which follows from the next meta-theorem:

\begin{thm}\label{thm_main_meta}
    Let $J$ be any set of jobs. Then for number of machines $m \geq 16$, we have $\lvert \textsc{LMNY}\xspace(J_{hi}) \rvert + \lvert \textsc{SRPT}\xspace(J_{lo}) \rvert + \lvert \textsc{MLax}\xspace(J_{lo}) \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J) \rvert)$, where $J_{hi} = \{j \in J \mid \ell_j > x_j \}$ and $J_{lo} = \{j \in J \mid \ell_j \leq x_j\}$ partition $J$ into high- and low-laxity jobs.
\end{thm}
\begin{proof}
    We have $\lvert \textsc{LMNY}\xspace(J_{hi}) \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J_{hi}) \rvert$ by \Cref{lem_LMNY}. Also, we further partition $J_{lo} = J_v \cup J_{nv}$ into the viable and non-viable jobs with respect to $\textsc{MLax}\xspace(J_{lo})$. Then \Cref{thm_srpt_nv_low} and \Cref{thm_viable} together give $\lvert \textsc{SRPT}\xspace(J_{lo}) \rvert + \lvert \textsc{MLax}\xspace(J_{lo}) \rvert = \Omega (\lvert \mbox{\rm Opt}\xspace(J_v) \rvert + \lvert \mbox{\rm Opt}\xspace(J_{nv}) \rvert)$. To complete the proof, we observe that $J = J_{hi} \cup J_v \cup J_{nv}$ partitions $J$, so $\lvert \mbox{\rm Opt}\xspace(J_{hi}) \rvert + \lvert \mbox{\rm Opt}\xspace(J_v) \rvert + \lvert \mbox{\rm Opt}\xspace(J_{nv}) \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J) \rvert)$.
\end{proof}

The proof of \Cref{thm_main_final}, which gives our performance guarantee for \textsc{FinalAlg}\xspace is immediate:

\begin{proof}[Proof of \Cref{thm_main_final}]
    By combining \Cref{thm_main_meta} and \Cref{lem_reduce_machine}, the objective value achieved by \textsc{FinalAlg}\xspace is:
    \begin{align*}
        \Omega(\lvert \textsc{LMNY}\xspace(J_{hi}, \frac{m}{3})\rvert + \lvert \textsc{SRPT}\xspace(J_{lo}, \frac{m}{3})\rvert + \lvert \textsc{MLax}\xspace(J_{lo}, \frac{m}{3})\rvert) &= \Omega( \lvert \mbox{\rm Opt}\xspace(J, \frac{m}{3}) \rvert)\\
        &= \Omega(\lvert \mbox{\rm Opt}\xspace(J,m) \rvert).
    \end{align*}
\end{proof}

Finally, we obtain our $O(1)$-competitive deterministic algorithm for all $m > 1$ (recall \textsc{FinalAlg}\xspace is $O(1)$-competitive only when $m \geq 48$) by using a two-machine algorithm when $m$ is too small:

\begin{proof}[Proof of \Cref{thm_main_deterministic}]
    Our algorithm is the following: If $1 < m < 48$, then we run the deterministic two-machine algorithm from \cite{KalyanasundaramP03} which is $O(1)$-competitive with the optimal single-machine schedule. Thus by \Cref{lem_reduce_machine}, this algorithm is also $O(m) = O(1)$-competitive for all $m < 48$. Otherwise, $m \geq 48$, so we run \textsc{FinalAlg}\xspace.
\end{proof}

\section{Introduction}\label{sec_intro}

We consider the basic problem of preemptively scheduling jobs that arrive online with sizes and deadlines on $m$ identical machines to maximize the number of jobs that complete by their deadline.

\begin{definition}[Throughput Maximization]\label{def_problem}
    Let $J$ be a collection of jobs such that each $j \in J$ has a \emph{release time} $r_j$, a \emph{processing time} (or \emph{size}) $x_j$, and a \emph{deadline} $d_j$. The jobs arrive online at their release times, at which the scheduler becomes aware of job $j$ and its $x_j$ and $d_j$.

    At each moment of time, the scheduler
    can specify up to $m$ released jobs to run
    at this time, and the remaining processing time
    of the  jobs that are run is decreased at a unit rate (so we assume that the online scheduler is allowed to produce a migratory schedule.) A job is completed if its remaining processing time drops to zero by the deadline of that job.
    The objective is to maximize the number completed jobs.

\end{definition}

A key concept in designing algorithms for this problem is the laxity of a job. The \emph{laxity} of a job $j$ is $\ell_j = (d_j - r_j) - x_j$, which is the maximum amount of time we can not run $j$ and still possibly complete it.

We measure the performance of our algorithm by the \emph{competitive ratio}, which is the maximum over all instances of the ratio of the objective value of our algorithm to the objective value of the optimal offline schedule that is aware of all jobs in advance.

\begin{comment}
    More specifically, each job $j$ has a {\em release time} $r_j$,
    a {\em size} or {\em processing time} $x_j$,  a {\em deadline} $d_j$, and  a {\em laxity} $\ell_i = (d_j - r_j) - x_j$.
    The online scheduler is unaware of job $j$ until
    time $r_j$, at which time the scheduler
    additionally learns $x_j$, $d_j$, and $\ell_j$.
    At each moment of time, the online algorithm
    can specify up to $m$ released jobs to run
    at this time, and the remaining processing time
    of the  jobs that are run is decreased at a unit rate (so we assume that the online scheduler is allowed to produce a migratory schedule.) A job is completed if its remaining processing time drops to zero by the deadline of that job.
    The objective is to maximize the number completed jobs. We consider the competitive ratio that
    is achievable by online algorithms for this problem.
\end{comment}

This problem is well understood for the $m=1$ machine case.
No $O(1)$-competitive deterministic algorithm is possible~\cite{BaruahKMMRRSW92},
but there is a randomized algorithm that is
$O(1)$-competitive against an oblivious adversary~\cite{KalyanasundaramP03},
and there is a scalable ($O(1+\epsilon)$-speed $O(1/\epsilon)$-competitive) deterministic algorithm~\cite{KalyanasundaramP00}. The scalability result in \cite{KalyanasundaramP00}
was extended  to the case of $m > 1 $ machines in \cite{LucierMNY13}.

Whether an $O(1)$-competitive algorithm exists for $m > 1$
machines has been open for twenty years. Previous results for the multiple machines setting require resource augmentation or assume that all jobs have high laxity \cite{LucierMNY13,EberleMS20}.

The main issue issue in removing these assumptions is
how to determine which machine
to assign a job to. If an online algorithm could determine which
machine each job was assigned to in \mbox{\rm Opt}\xspace, we could obtain an $O(1)$-competitive algorithm
for $m > 1$ machines by a relatively straight-forward
adaptation of the results from \cite{KalyanasundaramP03}.
However, if the online algorithm ends up assigning some jobs to different
machines than \mbox{\rm Opt}\xspace, then
comparing the number of completed jobs is challenging. Further, if jobs have small laxity, then the algorithm can be severely penalized for small mistakes in this assignment.
One way to view the speed augmentation (or high laxity assumption) analyses in \cite{LucierMNY13,EberleMS20} is that the speed augmentation assumption allows one to avoid having to address this issue in the analyses.

\subsection{Our Results}

Our main result is an  $O(1)$-competitive deterministic algorithm
for Throughput Maximization on $m>1$ machines.

\begin{thm}\label{thm_main_deterministic}
    For all $m > 1$, there exists a deterministic $O(1)$-competitive algorithm for Throughput Maximization on $m$ machines.
\end{thm}

We summarize our results and prior work in Table \ref{table}. Interestingly, notice that on a single machine there is no constant competitive deterministic algorithm, yet a randomized algorithm exists with constant competitive ratio.  Our work shows that once more than one machine is considered, then determinism is sufficient to get a $O(1)$-competitive online algorithm.

\begin{table}[h]
\begin{tabular}{|l|l|l|l|}
\hline
            & Deterministic & Randomized & \begin{tabular}[c]{@{}l@{}}Speed\\ Augmentation\end{tabular} \\ \hline
     \hline
     $m=1$       & $\omega(1)$   & $O(1)$    & $O(1+\epsilon)$-speed $O(1/\epsilon)$-competitive        \\
          &\cite{BaruahKMMRRSW92}   & \cite{KalyanasundaramP03}    & \cite{KalyanasundaramP00}        \\ \hline
 $m > 1$ &        $O(1)$       &      $O(1)$       & $O(1+\epsilon)$-speed $O(1/\epsilon)$-competitive        \\
 &           [This paper]    &     [This paper]       &  \cite{LucierMNY13}        \\
 \hline
\end{tabular}
\medskip
\caption{Competitiveness Results}
\label{table}
\end{table}

\subsection{Scheduling Policies}

We give some basic definitions and notations about scheduling policies.

A job $j$ is \emph{feasible} at time $t$ (with respect to some schedule) if it can still be feasibly completed, so $x_j(t) > 0$ and $t + x_j(t) \leq d_j$, where $x_j(t)$ is the remaining processing time of job $j$ at time $t$ (with respect to the same schedule.)

Then a schedule $\mathcal{S}$ of jobs $J$ is defined by a map from
time/machine pairs $(t, i)$ to a feasible job $j$
that is run on machine $i$ at time
$t$, with the constraint that no job can be
run one two different  machines at the same time. . We conflate $\mathcal{S}$ with the scheduling policy as well as the set of jobs \emph{completed} by the schedule. Thus, the objective value achieved by this schedule is $\lvert \mathcal{S} \rvert$.

A schedule is \emph{non-migratory} if for every job $j$  there exists a
machine $i$ such that if $j$ is run at time $t$ then $j$ is run on machine $i$. Otherwise the schedule is \emph{migratory}.

If $\mathcal{S}$ is a scheduling algorithm, then $\mathcal{S}(J,m)$
denotes the schedule that results from running $\mathcal S$
on instance $J$ on $m$ machines.
Similarly, $\mbox{\rm Opt}\xspace(J,m)$ denotes the optimal schedule on instance $J$ on $m$ machines. We will sometimes omit the $J$ and/or the $m$ if
they are clear from context. Sometimes we will abuse notation and let $\mbox{\rm Opt}\xspace$ denote a nearly-optimal schedule
that additionally has some desirable structural property.

\subsection{Algorithms and Technical Overview}

A simple consequence of the results in
\cite{KalyanasundaramP01} and \cite{KalyanasundaramP03} is
an $O(1)$-competitive algorithm in the case that $m =O(1)$.
Thus we concentrate on the case that $m$ is large.
Also note that since there is an $O(1)$-approximate
non-migratory schedule~\cite{KalyanasundaramP01},
changing the number of machines by an $O(1)$ factor
does not change the optimal objective value by
more than an $O(1)$ factor.
This is because we can always take an optimal non-migratory schedule on $m$ machines and create a new schedule on $m/c$  machines
whose objective value decreases by at most a factor of $c$,
by keeping the $m/c$ machines that complete the most jobs.

\begin{comment}
    First, by losing a $O(1)$-factor in the competitive ratio, we may assume the optimal schedule is non-migratory. It is shown in \cite{KalyanasundaramP01} that if there is a migratory schedule
    on $m$ identical machines that completes a set of jobs,
    then there is a non-migratory preemptive schedule on $6m-5$ machines
    that completes the same set of jobs.
\end{comment}

These observations about the structure of near-optimal
schedules allow us to design a
$O(1)$-competitive algorithm that is a combination of various
deterministic algorithms. In particular, on instance $J$ our algorithm, \textsc{FinalAlg}\xspace  will run a deterministic algorithm   \textsc{LMNY}\xspace
on $m/3$ machines on the
subinstance $J_{hi} = \{j \in J \mid \ell_j > x_j\}$  of high laxity jobs,
a deterministic algorithm \textsc{SRPT}\xspace
on $m/3$ machines on the subinstance $J_{lo} = \{j \in J \mid \ell_j \leq x_j\}$
   of low laxity jobs, and a deterministic algorithm \textsc{MLax}\xspace
on $m/3$ machines on the subinstance $J_{lo}$
   of low laxity jobs. Note that we run \textsc{SRPT}\xspace and \textsc{MLax}\xspace on the same jobs. To achieve this, if both algorithms decide to run the same job $j$, then the algorithm in which $j$ has shorter remaining processing time actually runs job $j$, and the other simulates running $j$.

We will eventually show that
for all instances, at least one of these three algorithms
is $O(1)$-competitive, from which our main result will follow. Roughly, each of the three algorithms is responsible for a different part of \mbox{\rm Opt}\xspace.

Our main theorem about \textsc{FinalAlg}\xspace is the following:

\begin{thm}\label{thm_main_final}
    For any $m \geq 48$, \textsc{FinalAlg}\xspace is a $O(1)$-competitive deterministic algorithm for Throughput Maximization on $m$ machines.
\end{thm}

We now discuss these
three component algorithms of \textsc{FinalAlg}\xspace.

\subsubsection{\textsc{LMNY}\xspace}

The algorithm \textsc{LMNY}\xspace is the algorithm from \cite{LucierMNY13}
with the following guarantee.

\begin{lem}\label{lem_LMNY}\cite{LucierMNY13}
    For any number of machines $m$, and any job instance $J$,
    \textsc{LMNY}\xspace is an $O(1)$-competitive deterministic algorithm
    on the instance $J_{hi}$.
\end{lem}

\subsubsection{\textsc{SRPT}\xspace}

The algorithm   \textsc{SRPT}\xspace
is a variation of the standard shortest remaining processing time algorithm:

\begin{definition}[\textsc{SRPT}\xspace]\label{def_srpt}
    At each time, run the $m$ feasible jobs with shortest remaining processing time. If there are less than $m$ feasible jobs, then all feasible jobs are run.
\end{definition}

We will show that \textsc{SRPT}\xspace is competitive with the low laxity jobs in that are not preempted in \mbox{\rm Opt}\xspace.

\subsubsection{\textsc{MLax}\xspace}

The final, most challenging, component algorithm of \textsc{FinalAlg}\xspace is \textsc{MLax}\xspace, which intuitively we want to be competitive on  low-laxity jobs
in \mbox{\rm Opt}\xspace that are preempted.

    To better understand the challenge
    of achieving this, consider $m=1$ and
    an instance of disagreeable jobs,
    which means that jobs with an earlier release time have a later
    deadline. Further, suppose all jobs but one in \mbox{\rm Opt}\xspace is preempted and completed at a later time.

     To be competitive, \textsc{MLax}\xspace must preempt almost all
     the jobs that it completes, but cannot afford to abandon
     too many jobs that it preempts. Because the
     jobs have low laxity, this can be challenging as
     it can only preempt each job for a small amount of time,
     and its hard to know which of the many options is
     the ``right'' job to preempt for.
     This issue was resolved in \cite{KalyanasundaramP03}
     for the case of $m=1$ machine, but the issue gets more challenging when $m > 1$, because we also have to choose the ``right'' machine to assign a job.

We now describe the algorithm \textsc{MLax}\xspace.
Let $\alpha = O(1)$ be a sufficiently large constant (chosen later.) \textsc{MLax}\xspace maintains $m$ stacks (last-in-first-out data structures) of jobs (one per machine), $H_1, \dots, H_m$. The stacks are initially empty. At all times, \textsc{MLax}\xspace runs the top job of stack $H_i$ on machine $i$. We define the \emph{frontier} $F$ to be the set consisting of the top job of each stack (i.e. all currently running jobs.) It remains to describe how the $H_i$'s are updated.

There are two types of events that cause \textsc{MLax}\xspace to update the $H_i$'s: reaching a job's pseudo-release time (defined below) or completing a job.

\begin{definition}[Viable Jobs and Pseudo-Release Time]\label{def_viable}
    The pseudo-release time (if it exists) $\tilde{r}_j$ of job $j$ is the earliest time in $[r_j, r_j + \frac{\ell_j}{2}]$ such that there are at least $\frac{7}{8}m$ jobs $j'$ on the frontier satisfying $\alpha x_{j'} \geq \ell_j$.

    We say a job $j$ is \emph{viable} if $\tilde{r}_j$ exists and \emph{non-viable} otherwise.
\end{definition}

At job $j$'s pseudo-release time (note $\tilde{r}_j$ can be determined online by \textsc{MLax}\xspace), \textsc{MLax}\xspace does the following:
\begin{enumerate}[a)]
    \item If there exists a stack whose top job $j'$ satisfies $\alpha x_j \leq \ell_{j'}$, then \emph{push} $j$ onto any such stack.\label{line_push}
    \item Else if there exist at least $\frac{3}{4} m$ stacks whose second-top job $j''$ satisfies $\alpha x_j \leq \ell_{j''}$ and further some such stack has top job $j'$ satisfying $\ell_j > \ell_{j'}$, then on such a stack with minimum $\ell_{j'}$, \emph{replace} its top job $j'$ by $j$. \label{line_replace}
\end{enumerate}
While the replacement operation in step \ref{line_replace} can be implemented as a pop and then push, we view it as a separate operation for analysis purposes.
To handle corner cases in these descriptions, one can assume that there is a job with infinite size/laxity on the  bottom of each $H_i$.

When \textsc{MLax}\xspace completes a job $j$ that was on stack $H_i$, \textsc{MLax}\xspace does the following:
\begin{enumerate}
    \item[c)] \emph{Pop} $j$ off of stack $H_i$.\label{line_completion_pop}
    \item[d)] Keep \emph{popping} $H_i$ until the top job of $H_i$ is feasible.\label{line_infeasible_pop}
\end{enumerate}

\subsubsection{Analysis Sketch}

There are three main steps in proving \Cref{thm_main_final} to show \textsc{FinalAlg}\xspace is $O(1)$-competitive:
\begin{itemize}
    \item In \Cref{sec_prelim}, we show how to modify the optimal schedule to obtain certain structural properties that facilitate the comparison with \textsc{SRPT}\xspace and \textsc{MLax}\xspace.
    \item In \Cref{sec_nonviable}, we show that \textsc{SRPT}\xspace is competitive with the low-laxity, non-viable jobs.
    Intuitively, the jobs that \textsc{MLax}\xspace is running that prevent
    a job $j$ from becoming viable are so much smaller than
    job $j$, and they provide a witness that \textsc{SRPT}\xspace must also be working on jobs much smaller than $j$.

    \item In \Cref{sec_viable}, we show that \textsc{SRPT}\xspace and \textsc{MLax}\xspace together are competitive with the low-laxity, viable jobs.
    First, we show that \textsc{SRPT}\xspace is competitive with the number of
    non-preempted jobs in \mbox{\rm Opt}\xspace. We then essentially show that \textsc{MLax}\xspace is
    competitive with the number of preempted jobs in \mbox{\rm Opt}\xspace.
    The key component is the design of \textsc{MLax}\xspace is the condition
    that a job $j$ won't replace a job on the frontier unless
    at there are at least $\frac{3}{4} m$ stacks whose second-top job $j''$ satisfies $\alpha x_j \leq \ell_{j''}$. This is the condition that intuitively most differentiates the \textsc{MLax}\xspace from
    $m$ copies of the \textsc{Lax}\xspace algorithm in \cite{KalyanasundaramP03}. This also is the
    condition that allows us to surmount the issue of potentially assigning a job to a ``wrong'' processor. Jobs that satisfy this condition are highly flexible about where they can go on the frontier. Morally, our analysis shows that a constant fraction of the jobs that \mbox{\rm Opt}\xspace preempts and completes must be such flexible jobs.
\end{itemize}

We combine these results in \Cref{sec_final} to complete the analysis of \textsc{FinalAlg}\xspace.

\begin{comment}
    Our algorithm \textsc{FinalAlg}\xspace  will, with probability $1/3$,
    use the  \textsc{LMNY}\xspace algorithm from
    \cite{LucierMNY13} on the collection $\mathcal{HL}\xspace$ of high laxity jobs,
     which are the jobs whose initial
    laxity is at least  the  size of the job,
    to produce a schedule \textsc{LMNY}\xspace($\mathcal{HL}\xspace$).
    Thus the hard case that remains is for us to design an
    $O(1)$-competitive algorithm for  low laxity jobs.
    Our starting point for this will be
    the algorithm for $m=1$ machine in
    \cite{KalyanasundaramP03}, which runs each of two deterministic algorithms with probability $1/2$.
    The first algorithm is (a variation of)
    the standard Shortest Remaining Processing Time (\textsc{SRPT}\xspace) algorithm,
    which always runs the (at most)
    $m$ unfinished jobs with nonnegative laxity that have the least remaining
    processing time.
    The second algorithm is called \textsc{Lax}\xspace. which will
    discuss in a moment.

    Eventually our
    algorithm \textsc{FinalAlg}\xspace will with probability $1/3$
    run the
    algorithm \textsc{SRPT}\xspace on the collection $\mathcal{LL}\xspace$ of
    low laxity jobs, which are jobs whose initial laxity
    is at most their size, producing the schedule
    \textsc{SRPT}\xspace($\mathcal{LL}\xspace$).
    And our algorithm \textsc{FinalAlg}\xspace will with probability $1/3$
    run the
    algorithm \textsc{MLax}\xspace, which is conceptually
    running a simplified version
    of the algorithm \textsc{Lax}\xspace from \cite{KalyanasundaramP03}
    on each machine,
    on the collection $\mathcal{LL}\xspace$ of
    low laxity jobs producing the schedule
    \textsc{MLax}\xspace($\mathcal{LL}\xspace$).

    The main issue issue in the design and analysis of
    \textsc{MLax}\xspace is how to determine which machine
    to assign a job to. If an online algorithm could determine which
    machine each job was assigned to in the optimal nonmigratory
    schedule, we could obtain an $O(1)$-competitive algorithm
    for $m > 1$ machines by a relatively straight-forward
    adaptation of the results from \cite{KalyanasundaramP03}.
    But if the online algorithm ends up assigning some jobs to different
    machines than in the optimal nonmigratory schedule, then
    comparing the number of completed jobs is
     challenging.  This is presumably
    why the problem is still open.
    One way to view the speed augmentation (or high
    laxity assumption) analyses in \cite{LucierMNY13,EberleMS20} is that
    the speed augmentation assumption allows
    one to avoid having to address this issue in the analyses.

    Before we can understand how we surmount this issue,
    we need to state the simplified version of the
    $m=1$ machine algorithm \textsc{Lax}\xspace from \cite{KalyanasundaramP03}
    that we use.
    The algorithm \textsc{Lax}\xspace maintains a stack of jobs $H$
    and maintains the invariant that it is always running
    the job at the top of $H$. \textsc{Lax}\xspace changes states
    in the response to two types of events, the
    (perceived) release of a job, and the completion
    of the top job on $H$. In response to the (perceived)
    release of a job $j$
    \textsc{Lax}\xspace takes the following actions ($\alpha$ is some sufficiently large constant, it will be sufficient to take $\alpha = 24$):
    \begin{mdframed}
    \noindent {\bf \textsc{Lax}\xspace Algorithm Description:}
    \begin{itemize}
    \item
    In response to the (perceived)
    release of a job $j$
    \textsc{Lax}\xspace takes the following actions ($\alpha$ is some sufficiently large constant, it will be sufficient to take $\alpha = 24$):
    \begin{enumerate}[a)]
    \item
    Let $i$ be the job on the top of $H$ and $h$
    the job right below $i$ on $H$.
        \item If $x_j \le \alpha \ell_i$ is pushed onto the top of $H$.
        \item Else if  $\ell_j > \ell_{i}$ and  $\alpha x_j \leq \ell_{h}$ then job $i$ is replaced
        by job $j$ on the top of $H$. Note that this replacement operation does not count as either a push or a pop, it is a separate stack operation.
    \end{enumerate}
    \item
    In response to the completion of the job $i$ at
    the top of the stack $H$ at time $t$, \textsc{Lax}\xspace iteratively
    pops jobs off the top of $H$ until
    the top job $i$ on $H$ may still possibly be completed
    by its deadline (so the remaining processing time
    for job $i$ is at most $d_i - t$).
    \end{itemize}
    \end{mdframed}
    To handle corner cases in these descriptions,
        one can assume that there is a job with infinite laxity/deadline on the  bottom of $H$.

    To surmount this issue, our algorithm \textsc{MLax}\xspace classifies some jobs
    as being inviable for some period of time after they are released.
    A job $j$ is inviable until such time $\tilde r_j$
    as there are $3m/4$
    machines $P$ where the job $i$ on the top of
    the stack in the copy of \textsc{Lax}\xspace on $P$ satisfies
    $\alpha x_i \le \ell_j$.
    The time $\tilde r_j$ is called the pseudo-release time
    of job $j$. If a job $j$ does not
    become viable before time $r_j + \ell_j/2$,
    then it becomes permanently inviable,
    and its pseudo-release time is infinite.
    A job that is inviable is essentially invisible to the
    copies of \textsc{Lax}\xspace running on each machine.
    If and when a job $j$ becomes viable
    at a time $\tilde r_j$, \textsc{MLax}\xspace follows the following
    iterative process. On each iteration there is a job
    $k$ that \textsc{MLax}\xspace is considering adding to the frontier.
    Initially the job $k$ is equal to the job $j$ whose
    pseudo-release time triggered this.
    The job $k$ is offered to each copy of the \textsc{Lax}\xspace
    algorithm, which acts as if job $k$ was released at this time.
    In response to the perceived release of job
    $k$,
    multiple copies of \textsc{Lax}\xspace may want to push job $k$
    onto their stack. In this case the algorithm \textsc{MLax}\xspace
    then selects an arbitrary copy of \textsc{Lax}\xspace that
    is allowed to push $k$ onto its stack.
    In this case the iterative process triggered by $j$'s release is
    terminated.
    Otherwise in response to the perceived release of job
    $k$,
    multiple copies of \textsc{Lax}\xspace may want to replace a job
    at the top of their stack with $k$. In this case the algorithm \textsc{MLax}\xspace
    then selects an the copy of \textsc{Lax}\xspace whose top
    job has the lowest laxity and that copy of \textsc{Lax}\xspace
    is allowed to replace the job on the top of its stack
    with $k$. Let $f$ be the job that is replaced by job
    $k$. Then on the next iteration the job $k$ is set to $f$.

    Now we give an overview of the analysis of \textsc{FinalAlg}\xspace:
    \begin{itemize}
    \item
    From the results in \cite{LucierMNY13}
    we know that $| \textsc{LMNY}\xspace(\mathcal{HL}\xspace)| = \Omega( \mbox{\rm Opt}\xspace(\mathcal{HL}\xspace))$.
     \item
    In section \ref{sect:srptinviable}, we
    show that $| \textsc{SRPT}\xspace(\mathcal{LL}\xspace) | = \Omega(\mbox{\rm Opt}\xspace(\mathcal{N}\xspace))$, where
    $\mathcal{N}\xspace$ is collection of low laxity jobs
    that never become viable.
        \item In section \ref{sect:srptleaves}, we show that $ |\textsc{SRPT}\xspace(\mathcal{LL}\xspace) | = \Omega(\lambda))$,
        where $\lambda$ is number of nonpreempted jobs
        in $\mbox{\rm Opt}\xspace(\mathcal{LL}\xspace)$.
     \item
        In section \ref{sect:laxpushLP}, we show that
        $\lambda + \rho = \Omega(|\mbox{\rm Opt}\xspace(\mathcal{LL}\xspace)|)$,
        where $\rho$ is that aggregate number  pushes  \textsc{MLax}\xspace would execute if run.
        \item
        In section \ref{sect:laxpushUB}, we show that $|\textsc{SRPT}\xspace(\mathcal{LL}\xspace)| + |\textsc{MLax}\xspace(\mathcal{LL}\xspace)| = \Omega(\rho)$.
    \end{itemize}
    The fact that $|\textsc{SRPT}\xspace(\mathcal{LL}\xspace)| + |\textsc{MLax}\xspace(\mathcal{LL}\xspace)|  = \Omega(|Opt(\mathcal{LL}\xspace)|)$ then follows simple algebra,
    and the fact the \textsc{FinalAlg}\xspace is $O(1)$-competitive
    follows from combining the analyses of \textsc{LMNY}\xspace,
    \textsc{MLax}\xspace, and \textsc{SRPT}\xspace.
    The analyses of \textsc{SRPT}\xspace in section
    \ref{sect:srptinviable} and section \ref{sect:srptleaves} are relatively straight-forward generalizations of similar results
    in \cite{KalyanasundaramP03}. While statements
    similar to the main results in section
    \ref{sect:laxpushLP} and section \ref{sect:laxpushUB} appear in
    the analysis in \cite{KalyanasundaramP03},
    our proofs are substantially different, and rely
    critically on the viability criteria in \textsc{MLax}\xspace.
    So intuitively our analysis of \textsc{SRPT}\xspace and \textsc{MLax}\xspace
    relies on two facts:
    \begin{itemize}
        \item
    Jobs that never become viable are
    too large to beat \textsc{SRPT}\xspace, even if they were
    scheduled optimally,  and
    \item
    as a job
    that become viable is acceptable to half of the
    copies of \textsc{Lax}\xspace,  if this job was  not completed my \textsc{MLax}\xspace,
    \textsc{MLax}\xspace and \textsc{SRPT}\xspace together had better choices on a constant
    fraction of the machines, so completing this job wasn't vital.
    \end{itemize}
\end{comment}

\begin{comment}
\section{Formal Definitions}
\label{sec:background}

THIS SECTION STILL NEEDS WORK. BUT THIS CAN WAIT UNTIL ALMOST THE END.

A job $j$ is feasible at time $t$ (with respect to some schedule) if it can still be feasibly completed, so $t + x_j(t) \leq d_j$.

\begin{comment}
        A {\it migratory schedule} $S$ on $m$ machines
        is a partial function that maps each time $t \ge 0$ to
        a collection of up to $m$ jobs $i$ such that
        $r_i \le t \le d_i$, such that $S$ is running at time
        $t$. A {\it nonmigratory schedule} $S$ on $m$ machines
        is a partial function that maps each time $t \ge 0$
        and each machine $P$ to
        to a job $i$ such that
        $r_i \le t \le d_i$, that machine $P$ is running at time $t$,
        subject to the restriction that every time a job is run, it must
        be run on the same machine as it was last run.
    \end{comment}

    \begin{comment}
        A job $i$ is completed by a schedule $S$ if it
        is run for $x_i$ units of time during $[r_i, d_i]$.
        The objective that we consider in this paper is maximizing
        the number of completed jobs.
    \end{comment}

    If $S$ is a schedule,
    let $|S|$ be the number of jobs completed in $S$.
    If $\rm A$ is a scheduling algorithm, we let
    ${\rm A}(\mathcal{K})$ denote the schedule produced by ${\rm A}$ on
    input $\mathcal{K}$. We let $\mbox{\rm Opt}\xspace(\mathcal{K})$ denote the optimal
    schedule on an instance $\mathcal{K}$.

    \begin{comment}
        In this paper we use competitiveness in
        several different ways.
        A schedule $S$ is $c$-competitive
        with another schedule $T$ if $|T| \le c |S|$.
        A scheduling algorithm $\rm A$ is $c$-competitive
        if ${\rm A}(\mathcal{K})$ is $c$-competitive with $\mbox{\rm Opt}\xspace(\mathcal{K})$ for
        all inputs $\mathcal{K}$.
        A scheduling algorithm $\rm A$ is {\em competitive}
        if there exists some constant $c$ such that $\rm A$ is
        $c$-competitive.
        The {\em competitive ratio} of a scheduling algorithm $\rm A$
        is the minimum $c$, such that $\rm A$ is $c$-competitive.
        The competitive ratio can be viewed as the payoff to a game
        played between two players, the online player and the adversary.
        The adversary specifies the input and services that input optimally.
    \end{comment}

    A schedule $S$ is {\em resolute} if $S$ completes every job
    that it runs.
    We say that $S \subseteq T$ if every job completed in
    $S$ is completed in $T$.
    If $S$ runs a job $J_i$ then we denote the last time that $J_i$ is
    run as
    $c_i(S)$.
    If $S$ completes a job $J_i$ then $c_i(S)$ is the {\em completion
    time} of $J_i$.
    If $S$ runs a job $J_i$ then we denote the first time that $J_i$
    is run as
    $f_i(S)$.
    A job $J_i$ completed in a schedule $S$ is {\em idle}
    if the machine is idle for some non-zero amount of time between when $J_i$
    is first run and when $J_i$ is completed.
    We say a schedule $S$ is {\em efficient} if
    whenever there is a job that may still complete by its deadline in $S$,
    $S$ is running some such job, that is, $S$ never unnecessarily idles
    the machine.

     We say a single-machine schedule $\mathcal{S}$ is a forest schedule if for all jobs $j,j'$ such that $f_j(\mathcal{S}) < f_{j'}(\mathcal{S})$, then $\mathcal{S}$ does not run $j$ during the time interval $(f_{j'}(\mathcal{S}), c_{j'}(\mathcal{S}))$ (so the $(f_j(\mathcal{S}), c_j(\mathcal{S}))$-intervals form a laminar family.) Then $\mathcal{S}$ naturally defines a forest (in the graph-theoretic sense), where the nodes are jobs run by $\mathcal{S}$ and the descendants of a job $j$ are the the jobs that are first run in the time interval $(f_j(\mathcal{S}), c_j(\mathcal{S}))$.
    A non-migratory $m$-machine schedule is a forest schedule if all of its single-machine schedules are forest schedules.
    Because the Earliest Deadline First (EDF) algorithm
    feasible completes all jobs on one machine if there
    is a feasible schedule on one machine, the optimal non-migratory
    schedule is a forest schedule.

\end{comment}

\subsection{Related Work}

There is a line of papers that consider a dual
version of the problem, where there is a constraint that all jobs
must be completed by their deadline, and the objective is to minimize
the number of machines used~\cite{PhillipsSTW02,CMS18,AzarC18,ImMPS17}.
The current best known bound on the competitive ratio for this version is $O(\log \log m)$
from \cite{ImMPS17}.

The speed augmentation results in \cite{KalyanasundaramP00,LucierMNY13} for throughput can be generalized to weighted
throughput, where there a profit for each job, and the objective is
to maximize the aggregate profit of jobs completed by their deadline.
But without speed augmentation, $O(1)$-approximation is not possible
for weighted throughput for any $m$, even allowing
randomization~\cite{KorenS94}.

There is also a line of papers that consider variations on
online throughput scheduling in which the
online scheduler has to commit to completing jobs at some point in time,
with there being different variations of when commitment is required~\cite{LucierMNY13,EberleMS20,ChenEMSS20}.
For example, \cite{EberleMS20} showed that there is a scalable
algorithm for online throughput maximization that commits to finishing
every job that it begins executing.
\section{\textsc{SRPT}\xspace and \textsc{MLax}\xspace are Competitive with Viable Jobs}\label{sec_viable}

We have shown that \textsc{SRPT}\xspace is competitive with the non-viable, low-laxity jobs. Thus, it remains to account for the viable, low-laxity jobs. We recall that a job $j$ is viable if there exists a time in $[r_j, r_j + \frac{\ell_j}{2}]$ such that there are at least $\frac{7}{8}m$ jobs $j'$ on the frontier satisfying $\alpha x_{j'} \geq \ell_j$. The first such time is the pseudo-release time, $\tilde{r}_j$ of job $j$. For these jobs, we show that \textsc{SRPT}\xspace and \textsc{MLax}\xspace together are competitive with the viable, low-laxity jobs of the optimal schedule.

\begin{thm}\label{thm_viable}
    Let $J$ be a set of jobs satisfying $\ell_j \leq x_j$ for all $j \in J$. Then for $\alpha = O(1)$ sufficiently large and number of machines $m \geq 8$, we have $\lvert \textsc{SRPT}\xspace(J) \rvert + \lvert \textsc{MLax}\xspace(J) \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J_v) \rvert)$, where $J_v$ is the set of viable jobs with respect to $\textsc{MLax}\xspace(J)$.
\end{thm}
\begin{proof}[Proof of \Cref{thm_viable}]
    Let $\mathcal{S}, \mathcal{S}'$ be the schedules guaranteed by \Cref{lem_opt_struct} on the set of jobs $J_v$ with $\hat{r}_j = \tilde{r}_j$ for all $j \in J_v$. We re-state the properties of these schedules for convenience:
    \begin{enumerate}
        \item Both $\mathcal{S}$ and $\mathcal{S}'$ complete every job they run.
        \item Let $J_i$ be the set of jobs that $\mathcal{S}$ runs on machine $i$. For every machine $i$ and time, if there exists a feasible job in $J_i$, then $\mathcal{S}$ runs such a job.
        \item For all jobs $j \in \mathcal{S}$, we have $f_j(\mathcal{S}) = \tilde{r}_j$.
        \item If job $j'$ is a descendant of job $j$ in $\mathcal{S}$, then $\alpha x_{j'} \leq \ell_j$
        \item $\lvert \{\text{leaves of $\mathcal{S}'$}\}\rvert + \lvert \mathcal{S} \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J_v) \rvert)$.
    \end{enumerate}
    By \Cref{lem_srpt_leaves}, we have $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega (\lvert \{\text{leaves of $\mathcal{S}'$}\}\rvert)$. Thus, it suffices to show that $\lvert \textsc{SRPT}\xspace(J) \rvert + \lvert \textsc{MLax}\xspace(J) \rvert = \Omega(\lvert \mathcal{S} \rvert)$. We do this with two lemmas, whose proofs we defer until later. First, we show that \textsc{MLax}\xspace pushes (not necessarily completes) many jobs. In particular, we show:

    \begin{lem}\label{lem_lax_push}
        $\lvert \textsc{SRPT}\xspace(J) \rvert + \#(\text{pushes of $\textsc{MLax}\xspace(J)$}) = \Omega(\lvert \mathcal{S} \rvert)$
    \end{lem}

    The main idea to prove \Cref{lem_lax_push} is to consider sequences of preemptions in \mbox{\rm Opt}\xspace. In particular, suppose \mbox{\rm Opt}\xspace preempts job $a$ for $b$ and then $b$ for $c$. Roughly, we use viability to show that the only way \textsc{MLax}\xspace doesn't push any of these jobs is if in between their pseudo-release times, \textsc{MLax}\xspace pushes $\Omega(m)$ jobs.

    Second, we show that the pushes of \textsc{MLax}\xspace give a witness that \textsc{SRPT}\xspace and \textsc{MLax}\xspace together actually complete many jobs.

    \begin{lem}\label{lem_lax_srpt_complete}
        $\lvert \textsc{SRPT}\xspace(J) \rvert + \lvert \textsc{MLax}\xspace(J) \rvert = \Omega(\#(\text{pushes of $\textsc{MLax}\xspace(J)$}))$.
    \end{lem}

    The main idea to prove \Cref{lem_lax_srpt_complete} is to upper-bound the number of jobs that \textsc{MLax}\xspace pops because they are infeasible (all other pushes lead to completed jobs.) The reason \textsc{MLax}\xspace pops a job $j$ for being infeasible is because while $j$ was on a stack, \textsc{MLax}\xspace spent at least $\frac{\ell_j}{2}$ units of time running jobs higher than $j$ on $j$'s stack. Either those jobs are completed by \textsc{MLax}\xspace, or \textsc{MLax}\xspace must have have done many pushes or replacements instead. We show that the replacements give a witness that \textsc{SRPT}\xspace must complete many jobs.

    Combining these two lemmas completes the proof of \Cref{thm_viable}.
\end{proof}

Now we go back and prove \Cref{lem_lax_push} and \Cref{lem_lax_srpt_complete}.

\subsection{Proof of \Cref{lem_lax_push}}

Recall that $\mathcal{S}$ is a forest schedule. We say the \emph{first child} of a job $j$ is the child $j'$ of $j$ with the earliest starting time $f_{j'}(\mathcal{S})$. In other words, if $j$ is not a leaf, then its first child is the first job that pre-empts $j$. We first focus on a sequence of first children in $\mathcal{S}$.

\begin{lem}\label{lem_lax_single_push}
Let $a,b,c \in \mathcal{S}$ be jobs such that $b$ is the first child of $a$ and $c$ is the first child of $b$. Then $\textsc{MLax}\xspace(J)$ does at least one of the following during the time interval $[\tilde{r}_a, \tilde{r}_c]$:
\begin{itemize}
    \item Push at least $\frac{m}{8}$ jobs
    \item Push job $b$
    \item Push a job on top of $b$ when $b$ is on the frontier
    \item Push $c$
\end{itemize}
\end{lem}
\begin{proof}
    By the properties of $\mathcal{S}$, we have $\tilde{r}_a < \tilde{r}_b < \tilde{r}_c$. It suffices to show that if during $[\tilde{r}_a, \tilde{r}_c]$, $\textsc{MLax}\xspace(J)$ pushes strictly fewer than $\frac{m}{8}$ jobs, $\textsc{MLax}\xspace(J)$ does not push $b$, and $\textsc{MLax}\xspace(J)$ does not push any job on top of $b$ if $b$ is on the frontier, then $\textsc{MLax}\xspace(J)$ pushes $c$.

    First, because $\textsc{MLax}\xspace(J)$ pushes strictly fewer than $\frac{m}{8}$ jobs during $[\tilde{r}_a, \tilde{r}_c]$, there exists at least $\frac{7}{8} m$ stacks that receive no push during this interval. We call such stacks \emph{stable}. The key property of stable stacks is that the laxities of their top- and second-top jobs never decrease during this interval, because these stacks are only changed by replacements and pops.

    Now consider time $\tilde{r}_a$. By definition of pseudo-release time, at this time, there exist at least $\frac{7}{8} m$ stacks whose top job $j'$ satisfies $\alpha x_{j'} \geq \ell_j$. Further, for any such stack, let $j''$ be its second-top job. Then because $b$ is a descendant of $a$ in $\mathcal{S}$, we have:
    \[\alpha x_b \leq \ell_a \leq \alpha x_{j'} \leq \ell_{j''}.\]
    It follows, there exist at least $\frac{3}{4}m$ stable stacks whose second-top job $j''$ satisfies $\alpha x_b \leq \ell_{j''}$ for the entirety of $[\tilde{r}_a, \tilde{r}_c]$. We say such stacks are $b$-stable.

    Now consider time $\tilde{r}_b$. We may assume $b$ is not pushed at this time. However, there exist at least $\frac{3}{4}m$ that are $b$-stable. Thus, if we do not replace the top of some stack with $b$, it must be the case that the top job $j'$ of every $b$-stable stack satisfies $\ell_j' \geq \ell_b$. Because these stacks are stable, their laxities only increase by time $\tilde{r}_c$, so $\textsc{MLax}\xspace(J)$ will push $c$ on some stack at that time.

    Otherwise, suppose we replace the top job of some stack with $b$. In particular, $b$ is on the frontier at $\tilde{r}_b$. We may assume that no job is pushed directly on top of $b$. If $b$ remains on the frontier by time $\tilde{r}_c$, then $\textsc{MLax}\xspace(J)$ will push $c$, because $\alpha x_c \leq \ell_b$. The remaining case is if $b$ leaves the frontier in some time in $[\tilde{r}_b, \tilde{r}_c]$. We claim that it cannot be the case that $b$ is popped, because by (\ref{prop_efficient}), $\mathcal{S}$ could not complete $b$ by time $\tilde{r}_c$, so $\textsc{MLax}\xspace(J)$ cannot as well. Thus, it must be the case that $b$ is replaced by some job, say $d$ at time $\tilde{r}_d$. At this time, there exist at least $\frac{3}{4}m$ stacks whose second-top job $j''$ satisfies $\alpha x_d \leq \ell_{j''}$. It follows, there exist at least $\frac{m}{2}$ $b$-stable stacks whose second-top job $j''$ satisfies $\alpha x_d \leq \ell_{j''}$ at time $\tilde{r}_d$. Note that because $m \geq 8$, there exists at least one such stack, say $i$, that is not $b$'s stack. In particular, because $b$'s stack has minimum laxity, it must be the case that the top job $j'$ of stack $i$ satisfies $\ell_{j'} \geq \ell_b$. Finally, because stack $i$ is stable, at time $\tilde{r}_c$ we will push $c$.
\end{proof}

Now using the above lemma, we give a charging scheme to prove \Cref{lem_lax_push}. First note that by \Cref{lem_srpt_leaves}, we have $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega(\#(\text{leaves of $\mathcal{S}$}))$. Thus, it suffices to give a charging scheme such that each job $a \in \mathcal{S}$ begins with $1$ credit, and charges it to leaves of $\mathcal{S}$ and completions of $\textsc{MLax}\xspace(J)$ so that each job is charged at most $O(1)$ credits. Each job $a \in \mathcal{S}$ distributes its $1$ credit as follows:

    \begin{itemize}
        \item (Leaf Transfer) If $a$ is a leaf or parent of a leaf of $\mathcal{S}$, say $\ell$, then $a$ charges $\ell$ for $1$ credit.
    \end{itemize}
        Else let $b$ be the first child of $a$ and $c$ the first child of $b$ in $\mathcal{S}$
        \begin{itemize}
            \item (Push Transfer)  If $\textsc{MLax}\xspace(J)$ pushes $b$ or $c$, then $a$ charges 1 unit to $b$ or $c$, respectively.
            \item (Interior Transfer) Else if job $b$ is on the frontier, but another job, say $d$, is pushed on top of $b$, then $a$ charges $1$ unit to $d$.
            \item ($m$-Push Transfer) Otherwise, by \Cref{lem_lax_single_push}, $\textsc{MLax}\xspace(J)$ must push at least $\frac{m}{8}$ jobs during $[\tilde{r}_a, \tilde{r}_c]$. In this case, $a$ charges $\frac{8}{m}$ units to each of these $\frac{m}{8}$ such jobs.
        \end{itemize}
    This completes the description of the charging scheme. It remains to show that each job is charged at most $O(1)$ credits. Each job receives at most $2$ credits due to Leaf Transfers and at most $2$ credits due to Push Transfers and Interior Transfers. As each job is in at most $3m$ intervals of the form $[\tilde{r}_a, \tilde{r}_c]$,  each job is charged $O(1)$ from $m$-Push Transfers.

\subsection{Proof of \Cref{lem_lax_srpt_complete}}

    Recall in \textsc{MLax}\xspace, there are two types of pops: a job is popped if it is completed, and then we continue popping until the top job of that stack is feasible. We call the former \emph{completion pops} and the later \emph{infeasible pops}. Note that it suffices to prove the next lemma, which bounds the infeasible pops. This is because $\#(\text{pushes of $\textsc{MLax}\xspace(J)$}) = \#(\text{completions pops of $\textsc{MLax}\xspace(J)$}) + \#(\text{infeasible pops of $\textsc{MLax}\xspace(J)$})$. To see this, note that every stack is empty at the beginning and end of the algorithm, and the stack size only changes due to pushes and pops.

    \begin{lem}\label{lem_lax_srpt_pop}
        For $\alpha = O(1)$ sufficiently large, we have: \[\lvert \textsc{SRPT}\xspace(J) \rvert + \lvert \textsc{MLax}\xspace(J) \rvert + \#(\text{pushes of $\textsc{MLax}\xspace(J)$}) \geq 2 \cdot \#(\text{infeasible pops of $\textsc{MLax}\xspace(J)$}).\]
    \end{lem}
        \begin{proof}
        We define a charging scheme such that the completions of $\textsc{SRPT}\xspace(J)$ and $\textsc{MLax}\xspace(J)$ and the pushes executed by $\textsc{MLax}\xspace(J)$  pay for the infeasible pops. Each completion of $\textsc{SRPT}\xspace(J)$ is given $2$ credits, each completion of $\textsc{MLax}\xspace(J)$ is given $1$ credit, and each job that $\textsc{MLax}\xspace(J)$ pushes is given $1$ credit. Thus each job begins with at most $4$ credits. For any $z \geq 0$, we say job $j'$ is $z$-below $j$ (at time $t$) if $j'$ and $j$ are on the same stack in $\textsc{MLax}\xspace(J)$ and $j'$ is $z$ positions below $j$ on that stack at time $t$. We define $z$-above analogously. A job $j$ distributes these initial credits as follows:
        \begin{itemize}
            \item(\textsc{SRPT}\xspace-transfer) If $\textsc{SRPT}\xspace(J)$ completes job $j$ and \textsc{MLax}\xspace~ also ran $j$ at some point, then $j$ gives $\frac{1}{2^{z+1}}$ credits to the job that is $z$-below $j$ at time $f_j(\textsc{MLax}\xspace(J))$ for all $z \geq 0$.
            \item($m$-\textsc{SRPT}\xspace-transfer) If $\textsc{SRPT}\xspace(J)$ completes job $j$ at time $t$, then $j$ gives $\frac{1}{2^{z+1}} \frac{1}{m}$ credits to the job that is $z$-below the top of each stack in $\textsc{MLax}\xspace(J)$ at time $t$ for all $z \geq 0$.
            \item(\textsc{MLax}\xspace-transfer) If $\textsc{MLax}\xspace(J)$ completes a job $j$, then $j$ gives $\frac{1}{2^{z+1}}$ credits to the job that is $z$-below $j$ at the time $j$ is completed for all $z \geq 0$.
            \item(Push-transfer) If $\textsc{MLax}\xspace(J)$ pushes a job $j$, then $j$ gives $\frac{1}{2^{z+1}}$ credits to the job that is $z$-below $j$ at the time $j$ is pushed for all $z \geq 0$.
        \end{itemize}

        It remains to show that for $\alpha = O(1)$ sufficiently large, every infeasible pop gets at least $4$ credits. We consider any job $j$ that is an infeasible pop of $\textsc{MLax}\xspace(J)$. At time $\tilde{r}_j$ when $j$ joins some stack in $\textsc{MLax}\xspace(J)$, say $H$, $j$'s remaining laxity was at least $\frac{\ell_j}{2}$. However, as $j$ later became an infeasible pop, it must be the case that while $j$ was on stack $H$, $\textsc{MLax}\xspace(J)$ was running jobs that are higher than $j$ on stack $H$ for at least $\frac{\ell_j}{2}$ units of time.

        Let $I$ be the union of intervals of times that $\textsc{MLax}\xspace(J)$ runs a job higher than $j$ on stack $H$ (so $j$ is on the stack for the entirety of $I$.) Then we have $\lvert I \rvert \geq \frac{\ell_j}{2}$. Further, we partition $I$ based on the height of the job
        on $H$ that $\textsc{MLax}\xspace(J)$ is currently running. In particular,
        we partition $I = \bigcup_{z \geq 1} I_z$, where $I_z$ is the union of intervals of times that $\textsc{MLax}\xspace(J)$ runs a job on $H$ that is exactly $z$-above $j$.

        By averaging, there exists a $z \geq 1$ such that $\lvert I_z \rvert \geq \frac{\ell_j}{2^{z+1}}$. Fix such a $z$. We can write $I_z$ as the union of disjoint intervals, say $I_z = \bigcup_{u = 1}^s [a_u, b_u]$.
        Because during each sub-interval, $\textsc{MLax}\xspace(J)$ is running jobs on $H$
        that are much smaller than $j$ itself, these jobs give a witness that $\textsc{SRPT}\xspace(J)$ completes many jobs as long as these sub-intervals are long enough.
        We formalize this in the following proposition.

        \begin{prop}\label{prop_subinterval_srpt}
            In each sub-interval $[a_u,b_u]$ of length at least $4\frac{\ell_j}{\alpha^z}$, job $j$ earns at least $\frac{1}{2^{z+3}} \frac{b_u - a_u}{\ell_j/\alpha^z}$ credits from \textsc{SRPT}\xspace-transfers and $m$-\textsc{SRPT}\xspace-transfers.
        \end{prop}
        \begin{proof}
            Because $[a_u,b_u]$ has length at least $4\frac{\ell_j}{\alpha^z}$, we can partition $[a_u,b_u]$ into sub-sub-intervals such that all but at most one sub-sub-interval has length exactly $2 \frac{\ell_j}{\alpha^z}$. In particular, we have at least $\frac{1}{2} \frac{b_u - a_u}{2 \ell_j / \alpha^z}$ sub-sub intervals of length exactly $2 \frac{\ell_j}{\alpha^z}$.

            Now consider any such sub-sub-interval. During this time, $\textsc{MLax}\xspace(J)$ only runs jobs on $H$ that are $z$-above  $j$. Let $J_z$ be the set of $z$-above jobs that $\textsc{MLax}\xspace(J)$ runs during $I_z$. For every job $j' \in J_z$, we have $x_{j'} \leq \frac{\ell_j}{\alpha^z}$. It follows that $j'$ is on  stack $H$ for at most $x_{j'} \leq \frac{\ell_j}{\alpha^z}$ units of time. In particular, $\textsc{MLax}\xspace(J)$ must \emph{start} a new $z$-above job, say $j'$, in the first half of the sub-sub-interval at some time, say $t$.

            At time $t$, $j'$ is feasible. There are two cases to consider. If $\textsc{SRPT}\xspace(J)$ also completes $j'$ at some time, then $j$ get $\frac{1}{2^{z+1}}$ credits from $j'$ in a \textsc{SRPT}\xspace-transfer. Otherwise if $\textsc{SRPT}\xspace(J)$ never completes $j'$, then  because $j'$ is feasible at $t$, it must be the case that $\textsc{SRPT}\xspace(J)$ completes $m$ jobs during the sub-sub-interval. Thus, $j$ gets $\frac{1}{m} \frac{1}{2^{z+1}}$ credits from $m$ separate $m$-\textsc{SRPT}\xspace-transfers during this sub-sub-interval. We conclude, job $j$ gets at least $\frac{1}{2^{z+1}}$ credits from at least $\frac{1}{2} \frac{b_u - a_u}{2 \ell_j / \alpha^z}$ sub-sub-intervals.
        \end{proof}

        On the other hand, even if the sub-intervals are too short, the job $j$ still gets credits from \textsc{MLax}\xspace-transfers and Push-transfers when the height of the stack changes.
        We formalize this in the following proposition.

        \begin{prop}\label{prop_subinterval_lax_push}
            For every sub-interval $[a_u,b_u]$, job $j$ earns at least $\frac{1}{2^{z+2}}$ credits from \textsc{MLax}\xspace-transfers and Push-transfers at time $b_u$.
        \end{prop}
        \begin{proof}
            Up until time $b_u$, $\textsc{MLax}\xspace(J)$ was running a $z$-above job on  stack $H$. At time $b_u$, the height of the stack $H$ must change. If the height decreases, then it must be the case that $\textsc{MLax}\xspace(J)$ completes the $z$-above job, so $j$ will get $\frac{1}{2^{z+1}}$ credits from a $\textsc{MLax}\xspace(J)$-transfer. Otherwise, the height increases, so $\textsc{MLax}\xspace(J)$~ must push a job that is $z+1$-above $j$, which gives $j$ $\frac{1}{2^{z+2}}$ credits from a Push-transfer.
        \end{proof}

        Now we combine the above two propositions to complete the proof
        of Lemma \ref{lem_lax_srpt_pop}. We say a sub-interval $[a_u,b_u]$ is \emph{long} if it has length at least $4\frac{\ell_j}{\alpha^z}$ (i.e. we can apply \Cref{prop_subinterval_srpt} to it) and \emph{short} otherwise. First, suppose the aggregate length of all long intervals it at least $4 \cdot 2^{z+3} \frac{\ell_j}{\alpha^z}$. Then by \Cref{prop_subinterval_srpt}, job $j$ gets at least $4$ credits from the long intervals. Otherwise, the aggregate length of all long intervals is less than $4 \cdot 2^{z+3} \frac{\ell_j}{\alpha^z}$. In this case, recall that the long and short intervals partition $I_z$, which has length at least $\frac{\ell_j}{2^{z+1}}$. It follows, the aggregate length of the short intervals is at least $\frac{\ell_j}{2^{z+1}} - 4 \cdot 2^{z+3} \frac{\ell_j}{\alpha^z}$. For $\alpha = O(1)$ large enough, we may assume the aggregate length of the short intervals is at least $4 \cdot 2^{z+2} \frac{4\ell_j}{\alpha^z}$. Because each short interval has length at most $4\frac{\ell_j}{\alpha^z}$, there are at least $4 \cdot 2^{z+2}$ short intervals. We conclude, by \Cref{prop_subinterval_lax_push}, job $j$ gets at least $4$ credits from the short intervals. We conclude, in either case job $j$ gets at least $4$ credits.
    \end{proof}

    \begin{comment}
        \begin{proof}[Proof of \Cref{lem_lax_srpt_push} using \Cref{lem_lax_srpt_pop}]
        If $\kappa \ge \rho$ then this follows by
        simple algebra. If $\kappa \le \rho$
        then this follows as $| \textsc{MLax}\xspace | = \Theta(\rho)$.
        \end{proof}
    \end{comment}

\begin{comment}
    This section is dedicated to proving
    Lemma \ref{lem_lax_push}.
    To accomplish this we first state
    an auxiliary lemma, namely Lemma \ref{lem_lax_single_push}, prove that
    Lemma \ref{lem_lax_single_push} implies
    Lemma \ref{lem_lax_push}, and then
    prove Lemma \ref{lem_lax_single_push}.
    Let \mbox{\rm Opt}\xspace be the optimal non-migratory
    schedule on low laxity jobs that never become
    viable. Let $\mathcal S$ be the scheduled
    derived by applying Lemma
    \ref{lem:optstruct} with $\mathcal{T} = \mbox{\rm Opt}\xspace$
    and each $\widehat r_i = \tilde r_i$.

    \begin{lem}\label{lem_lax_push}
       $\lambda + \rho = \Omega( \lvert \mbox{\rm Opt}\xspace \rvert)$.
    \end{lem}

    \begin{proof}[Proof of \Cref{lem_lax_push} using \Cref{lem_lax_single_push}] NEEDS TO BE UPDATED.
    Since by Lemma \ref{lem:optstruct} it
    is the case that $|\mathcal{S}| = \Omega(|\mbox{\rm Opt}\xspace|)$,
    it is sufficient to show
       $\lambda + \rho = \Omega( \lvert \mathcal{S} \rvert)$.
      To accomplish this we define a charging scheme, where each job
       $a \in \mathcal S$ charges 1 unit to the leaf of $\mathcal{S}$ and or 1 unit to some job pushed by \textsc{MLax}\xspace in the following manner:
        \begin{itemize}
            \item (Leaf Transfer) If $a$ is a leaf or parent of a leaf of $\mathcal{S}$, say $\ell$, then $a$ charges $\ell$ for 1 unit.
            \end{itemize}
            Else  let $b$ be the first child of $a$ and $c$ the first child of $b$.
            \begin{itemize}
            \item (Push Transfer)  If \textsc{MLax}\xspace~ pushes $c$, then $a$ charges 1 unit to $c$.
            \item (Interior Transfer) Else if job $b$
            is in the interior of one of the stacks in
            \textsc{MLax}\xspace at time $\tilde{r}_c$ then
            $a$ changes the push that moved $b$ from
            the frontier to the interior.
            \item ($m$-Push Transfer) Otherwise, by \Cref{lem_lax_single_push}, \textsc{MLax}\xspace~ must push at least $\frac{m}{4}$ jobs during $[\tilde{r}_a, \tilde{r}_c]$. In this case, $a$ charges $\frac{4}{m}$ units to each of these $\frac{m}{4}$ such jobs.
        \end{itemize}
        To establish the desired result it is sufficient to show that each job
        is charged $O(1)$ credits. Each job receives at most $2$ credits due to Leaf Transfers and at most $2$ credits due to Push Transfers and Interior Transfers. As each job is in at most $3m$ intervals of the
        form $[\tilde{r}_a, \tilde{r}_c]$,  each job is charged $O(1)$ from $m$-Push Transfers.
    \end{proof}
\end{comment}

\begin{comment}
    \begin{proof}[Proof of \Cref{lem_lax_single_push}]
        By the properties of $\mathcal{S}$, we have $\tilde{r}_a < \tilde{r}_b < \tilde{r}_c$.
        Also as $\mathcal{S}$ could not complete
        job $a$ by time $\tilde{r}_b$ and job $b$ by
        time $\tilde{r}_c$ then neither can \textsc{MLax}\xspace.
          If $b$ was pushed, $b$ was on the interior, or $m/8$ jobs
          were pushed
    in time during $[\tilde{r}_a, \tilde{r}_c]$ then we are done,
    so assume otherwise.
    Call a stack stable if it did not receive a push during
    the time interval $[\tilde{r}_a, \tilde{r}_c]$.
    Note that there are at least $7m/8$ stable stacks.
     Also note that the frontier of a stable stack can only change due to replacements and pops, and both of these operations
        can not decrease the laxity of the top and second-top jobs of the stack during the time interval  $[\tilde{r}_a, \tilde{r}_c]$.

        First we consider time $\tilde{r}_a$ in \textsc{MLax}\xspace. By the definition
        of $\tilde{r}_a$ at this time there are at least $\frac{3m}{4}$ jobs $j'$ on the frontier such that $\alpha x_{j'} \geq \ell_a$. Let $j'$ be an arbitrary such job,
        and let $j''$ be the second-top job on the \textsc{Lax}\xspace stack where $j'$ is the top job
        at time $\tilde{r}_a$.
        Because $b$ is a descendant of $a$ in $\mathcal{S}$, we have $\alpha x_b \leq \ell_a$. Thus:
       $\ell_{j''} \geq \alpha x_{j'} \geq \ell_a \geq \alpha x_b$.
        Thus at time $\tilde{r}_a$, there are at least $\frac{3m}{4}$ \textsc{Lax}\xspace stacks,
        which we call the \emph{good} stacks, where $\alpha x_b \leq \ell_{j''}$, where $j''$ is the second-top job on the stack.
      By the pigeon hole principle there exists at least $\frac{5m}{8}$ stable good stacks.

     We break the proof into cases.

    In the first case assume that  $b$ is on the frontier  at time $\tilde{r}_c$. In this case, \textsc{MLax}\xspace~ will push $c$ at time
        $\tilde{r}_c$, because $\alpha x_c \leq \ell_b$.

        In the second case assume  job $b$ was  not
        added to the frontier at time $\tilde{r}_b$.
        Thus for each of the good stable stacks $H$ we know that at
        time $\tilde{r}_b$
    that $\ell_b \le \ell_i$, where $i$ is the top job on $H$.
     Thus
        at time $\tilde{r}_c$, it is the case that job $c$
        can be pushed onto any of these good stable stacks.
        Thus at time $\tilde{r}_c$ the job $c$ will get
        popped onto some stack in \textsc{MLax}\xspace.

        In the third case assume that job $b$ was added
        to the frontier at time $\tilde{r}_b$, but
        was not on the frontier at time $\tilde{r}_c$.
       The only possible scenario to explain this
       is if job $b$ was replaced by a job, say $d$,
        at time $\tilde{r}_d \in [\tilde{r}_b, \tilde{r}_c]$.
        By the definition of the algorithm \textsc{MLax}\xspace
    if job $b$ left the frontier at time $\tilde{r}_d$ then
    it must be the case that for all the jobs $i$ in
    the frontier on a good stable stack that $\ell_i \ge \ell_b$.
    Thus
        at time $\tilde{r}_c$, it is the case that job $c$
        can be pushed onto any of these good stable stacks.
        Thus at time $\tilde{r}_c$ the job $c$ will get
        popped onto some stack in \textsc{MLax}\xspace.
    \end{proof}
\end{comment}

\begin{comment}

    The goal of this section is to prove
    Lemma \ref{lem_lax_srpt_push}.
    To accomplish this we first state
    an auxiliary lemma, namely Lemma \ref{lem_lax_srpt_pop}, prove that
    Lemma \ref{lem_lax_srpt_pop} implies
    Lemma \ref{lem_lax_srpt_push}, and then devote the bulk of the
    section to
    proving Lemma \ref{lem_lax_srpt_pop}.
    Let \mbox{\rm Opt}\xspace be the optimal non-migratory
    schedule on low laxity jobs that never become
    viable.
    Let $\kappa$ be the number of infeasible pops
    executed by \textsc{MLax}\xspace, which are
    pops where \textsc{MLax}\xspace
    did not complete the popped job.

\end{comment}

\section{Structure of Optimal Schedule}\label{sec_prelim}

The goal of this section is to introduce the key properties of (near-)optimal scheduling policies that we will use in our analysis.

For completeness, we show that by losing a constant factor in the competitive ratio, we can use a constant factor fewer machines than $\mbox{\rm Opt}\xspace$. This justifies \textsc{FinalAlg}\xspace running each of three algorithms on $\frac{m}{3}$ machines.

\begin{lem}\label{lem_reduce_machine}
    For any collection of jobs $J$, number of machines $m$, and $c  >1$, we have $\lvert \mbox{\rm Opt}\xspace(J, \frac{m}{c}) \rvert = \Omega( \frac{1}{c}\lvert \mbox{\rm Opt}\xspace(J, m) \rvert)$.
\end{lem}
\begin{proof}
    It is shown in \cite{KalyanasundaramP01} that for any schedule on $m$ machines, there exists a non-migratory schedule on at most $6m$ machines that completes the same jobs. Applied to $\mbox{\rm Opt}\xspace(J,m)$, we obtain a non-migratory schedule $\mathcal{S}$ on $6m$ machines with $\lvert \mathcal{S} \rvert = \lvert \mbox{\rm Opt}\xspace(J,m) \rvert$. Keeping the $\frac{m}{c}$ machines that complete the most jobs in $\mathcal{S}$ gives a non-migratory schedule on $\frac{m}{c}$ machines that completes at least $\frac{1}{6c}\lvert \mathcal{S} \rvert$ jobs.
\end{proof}

A non-migratory schedule on $m$ machines can be expressed as $m$ schedules, each on a single machine and a separate set of jobs. To characterize these single machine schedules, we introduce the concept of forest schedules. Let $\mathcal{S}$ be any schedule. For any job $j$, we let $f_j(\mathcal{S})$ and $c_j(\mathcal{S})$ denote the first and last times that $\mathcal{S}$ runs the job $j$, respectively. Note that $\mathcal{S}$ does not necessarily complete $j$ at time $c_j(\mathcal{S})$.

\begin{definition}[Forest Schedule]\label{def_forest_sched}
    We say a single-machine schedule $\mathcal{S}$ is a forest schedule if for all jobs $j,j'$ such that $f_j(\mathcal{S}) < f_{j'}(\mathcal{S})$, then $\mathcal{S}$ does not run $j$ during the time interval $(f_{j'}(\mathcal{S}), c_{j'}(\mathcal{S}))$ (so the $(f_j(\mathcal{S}), c_j(\mathcal{S}))$-intervals form a laminar family.) Then $\mathcal{S}$ naturally defines a forest (in the graph-theoretic sense), where the nodes are jobs run by $\mathcal{S}$ and the descendants of a job $j$ are the the jobs that are first run in the time interval $(f_j(\mathcal{S}), c_j(\mathcal{S}))$.

    Then a non-migratory $m$-machine schedule is a forest schedule if all of its single-machine schedules are forest schedules.
\end{definition}

With these definitions, we are ready to construct the near-optimal policies that we will compare \textsc{SRPT}\xspace and \textsc{MLax}\xspace to:

\begin{lem}\label{lem_opt_struct}
    Let $J$ be a set of jobs satisfying $\ell_j \leq x_j$ for all $j \in J$. Then for any times $\hat{r}_j \in [r_j, r_j + \frac{\ell_j}{2}]$ and constant $\alpha \geq 1$, there exist non-migratory forest schedules $\mathcal{S}$ and $\mathcal{S}'$ on the jobs $J$ such that:
    \begin{enumerate}
        \item Both $\mathcal{S}$ and $\mathcal{S}'$ complete every job they run.\label{prop_resolute}
        \item Let $J_i$ be the set of jobs that $\mathcal{S}$ runs on machine $i$. For every machine $i$ and time, if there exists a feasible job in $J_i$, then $\mathcal{S}$ runs such a job.\label{prop_efficient}
        \item For all jobs $j \in \mathcal{S}$, we have $f_j(\mathcal{S}) = \hat{r}_j$.\label{prop_start}
        \item If job $j'$ is a descendant of job $j$ in $\mathcal{S}$, then $\alpha x_{j'} \leq \ell_j$\label{prop_shrinking}
        \item $\lvert \{\text{leaves of $\mathcal{S}'$}\}\rvert + \lvert \mathcal{S} \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J) \rvert)$.\label{prop_leafy}
    \end{enumerate}
\end{lem}
\begin{proof}
    We modify the optimal schedule $\mbox{\rm Opt}\xspace(J)$ to obtain the desired properties. First, we may assume that $\mbox{\rm Opt}\xspace(J)$ is non-migratory by losing a constant factor (\Cref{lem_reduce_machine}.) Thus, it suffices to prove the lemma for a single machine schedule, because we can apply the lemma to each of the single-machine schedules in the non-migratory schedule $\mbox{\rm Opt}\xspace(J)$. The proof for the single-machine case follows from the modifications given in Lemmas 22 and 23 of \cite{KalyanasundaramP03}. We note that \cite{KalyanasundaramP03} only show how to ensure $f_j(\mathcal{S}) = t_j$ for a particular $t_j \in [r_j, r_j + \frac{\ell_j}{2}]$, but it is straightforward to verify that the same proof holds for any $t_j \in [r_j, r_j + \frac{\ell_j}{2}]$.
\end{proof}

Morally, the schedule $\mathcal{S}$ captures the jobs in \mbox{\rm Opt}\xspace that are preempted and $\mathcal{S'}$ captures the jobs in \mbox{\rm Opt}\xspace that are not preempted (i.e. the leaves in the forest schedule.)
\section{\textsc{SRPT}\xspace is Competitive with Non-Viable Jobs}\label{sec_nonviable}

The main result of this section is that \textsc{SRPT}\xspace is competitive with the number of non-viable, low-laxity jobs of the optimal schedule (\Cref{thm_srpt_nv_low}.) We recall that a job $j$ is non-viable if for \emph{every time} in $[r_j, r_j + \frac{\ell_j}{2}]$, there are at least $\frac{1}{8}m$ jobs $j'$ on the frontier of \textsc{MLax}\xspace satisfying $\alpha x_{j'} < \ell_j$.

\begin{thm}\label{thm_srpt_nv_low}
    Let $J$ be a set of jobs satisfying $\ell_j \leq x_j$ for all $j \in J$. Then for $\alpha = O(1)$ sufficiently large and number of machines $m \geq 16$, we have $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega( \lvert \mbox{\rm Opt}\xspace(J_{nv}) \rvert)$, where $J_{nv}$ is the set of non-viable jobs with respect to $\textsc{MLax}\xspace(J)$.
\end{thm}

In the remainder of this section, we prove \Cref{thm_srpt_nv_low}. The main idea of the proof is that for any non-viable job $j$, \textsc{MLax}\xspace is running many jobs that are much smaller than $j$ (by at least an $\alpha$-factor.) These jobs give a witness that \textsc{SRPT}\xspace must be working on these jobs or even smaller ones.

We begin with a lemma stating that \textsc{SRPT}\xspace is competitive with the leaves of any forest schedule. Intuitively this follows because whenever some schedule is running a feasible job, then \textsc{SRPT}\xspace~ either runs the same job or a job with shorter remaining processing time. We will use this lemma to handle the non-viable jobs that are not preempted.

\begin{comment}
    We show in Lemma \ref{lem_srpt_resp} that \textsc{SRPT}\xspace~ is competitive with the
    number of nonviable low-laxity jobs of the optimal nonmigratory schedule.
    Recall that a job is nonviable if
    there does not exists a time $t \in [r_j, r_j + \frac{\ell_j}{2}]$ such that at this time, there exist at least $\frac{m}{2}$ jobs $j'$ on the
    to of some \textsc{Lax}\xspace stack such that  $\alpha x_{j'} \geq \ell_j$.
\end{comment}

\begin{comment}
    The proof of Lemma \ref{lem_srpt_resp} will use results
    from \cite{KalyanasundaramP03} about the existence of near-optimal
    schedules with certain certain structural properties,
    which is stated in Lemma \ref{lem:optstruct}.
\end{comment}

\begin{comment}
    \begin{lem}
        \label{lem:optstruct}
        For each job $i$,
        let $\widehat r_i$ be an arbitrary time between
        the release time $r_i$ and time
        $r_i + \ell_i/2$.
        Let $\mathcal T$ be an arbitrary
        migratory schedule.
          There is a nonmigratory schedule
          $\mathcal S$ such that
          \begin{itemize}
              \item $\mathcal S$ never idles a machine if there is uncompleted job in $\mathcal S$ that can be feasibly run on that machine at that time.
                \item For every $j \in \mathcal{S}$, we have $f_j(\mathcal{S}) = \widehat r_j$.
                \item For all jobs $j \in \mathcal{S}$, every descendant $i$ of $j$ satisfies $\alpha x_{i} \leq \ell_j$.
                The number of jobs completed by
                $\mathcal S$ is a constant fraction
                of the number of jobs completed
                by $\mathcal T$. That is,
                $|\mathcal{S}| = \Omega(|\mathcal{T}|)$.
          \end{itemize}
            \begin{proof}
               This follows from the transformations to the optimal schedule performed in \cite{KalyanasundaramP03}. In particular, Lemmas 15 and 16.
        \end{proof}

    \end{lem}
\end{comment}

\begin{lem}\label{lem_srpt_leaves}
    Let $J$ be any set of jobs and $\mathcal{S}$ be any forest schedule on $m$ machines and jobs $J' \subset J$ that only runs feasible jobs. Let $L$ be the set of leaves of $\mathcal{S}$. Then $\lvert \textsc{SRPT}\xspace(J) \rvert \geq \frac{1}{2} \lvert L \rvert$
\end{lem}
\begin{proof}
    It suffices to show that $\lvert L \setminus \textsc{SRPT}\xspace(J) \rvert \leq \lvert \textsc{SRPT}\xspace(J) \rvert$. The main property of \textsc{SRPT}\xspace~ gives:

    \begin{prop}\label{prop_srpt_leaves}
        Consider any leaf $\ell \in L \setminus \textsc{SRPT}\xspace(J)$. Suppose $\mathcal{S}$ starts running $\ell$ at time $t$. Then \textsc{SRPT}\xspace~ completes $m$ jobs in the time interval $[f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$.
    \end{prop}
    \begin{proof}
        At time $f_\ell(\mathcal{S})$ in \textsc{SRPT}\xspace(J), job $\ell$ has remaining processing time at most $x_\ell$ and is feasible by assumption. Because $\ell \notin \textsc{SRPT}\xspace(J)$, there must exist a first time $t' \in [f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$ where $\ell$ is not run by $\textsc{SRPT}\xspace(J)$. At this time, $\textsc{SRPT}\xspace(J)$ must be running $m$ jobs with remaining processing time at most $x_\ell - (t' - f_\ell(\mathcal{S}))$. In particular, $\textsc{SRPT}\xspace(J)$ must complete $m$ jobs by time $f_\ell(\mathcal{S}) + x_\ell$.
    \end{proof}

    Using the proposition, we give a charging scheme: Each job $\ell \in L \setminus \textsc{SRPT}\xspace(J)$ begins with $1$ credit. By the proposition, we can find $m$ jobs that $\textsc{SRPT}\xspace(J)$ completes in the time interval $[f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$. Then $\ell$ transfers $\frac{1}{m}$ credits each to $m$ such jobs in \textsc{SRPT}\xspace.

    It remains to show that each $j \in \textsc{SRPT}\xspace(J)$ gets at most $1$ credit. Note that $j$ can only get credits from leaves $\ell$ such that $c_j(\textsc{SRPT}\xspace) \in [f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$. There are at most $m$ such intervals (at most one per machine), because we only consider leaves, whose intervals are disjoint if there are on the same machine.
\end{proof}

Now we are ready to prove \Cref{thm_srpt_nv_low}.

\begin{proof}[Proof of \Cref{thm_srpt_nv_low}]
    Let $\mathcal{S}, \mathcal{S}'$ be the schedules guaranteed by \Cref{lem_opt_struct} on the set of jobs $J_{nv}$ with $\hat{r}_j = r_j$ for all $j \in J_{nv}$. We re-state the properties of these schedules for convenience:
    \begin{enumerate}
        \item Both $\mathcal{S}$ and $\mathcal{S}'$ complete every job they run.
        \item Let $J_i$ be the set of jobs that $\mathcal{S}$ runs on machine $i$. For every machine $i$ and time, if there exists a feasible job in $J_i$, then $\mathcal{S}$ runs such a job.
        \item For all jobs $j \in \mathcal{S}$, we have $f_j(\mathcal{S}) = r_j$.
        \item If job $j'$ is a descendant of job $j$ in $\mathcal{S}$, then $\alpha x_{j'} \leq \ell_j$
        \item $\lvert \{\text{leaves of $\mathcal{S}'$}\}\rvert + \lvert \mathcal{S} \rvert = \Omega(\lvert \mbox{\rm Opt}\xspace(J_{nv}) \rvert)$.
    \end{enumerate}
    By \Cref{lem_srpt_leaves}, we have $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega (\lvert \{\text{leaves of $\mathcal{S}'$}\}\rvert)$. Thus, it remains to show the following:

    \begin{lem}\label{lem_srpt_resp}
        For $\alpha = O(1)$ sufficiently large, $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega(\lvert \mathcal{S} \rvert)$
    \end{lem}
    \begin{proof}
        We first show that for the majority of jobs $j$ in $\mathcal{S}$'s forest, we run $j$ itself on some machine for at least a constant fraction of the time interval $[r_j, r_j + \frac{\ell_j}{2}]$.

        \begin{prop}\label{prop_find_interval}
            For at least half of the nodes $j$ in $\mathcal{S}$'s forest, there exists a closed interval $I_j \subset [r_j, r_j + \frac{\ell_j}{2}]$ of length at least $\frac{\ell_j}{8}$ such that $\mathcal{S}$ runs $j$ on some machine during $I_j$.
        \end{prop}
        \begin{proof}
            We say a node $j$ is a \emph{non-progenitor} if $j$ has less than $2^z$ descendants at depth $z$ from $j$ for all $z \geq 1$. Because $\mathcal{S}$ satisfies (\ref{prop_resolute}), at least half of the nodes in $\mathcal{S}$'s forest are non-progenitors. This follows from Lemma 7 in \cite{KalyanasundaramP03}.

            Now consider any non-progenitor node $j$. Because $\mathcal{S}$ is a forest, $\mathcal{S}$ is only running $j$ or its descendants on some machine in times $[r_j, r_j + \frac{\ell_j}{2}]$. Further, because $j$ is a non-progenitor and $\mathcal{S}$ satisfies (\ref{prop_resolute}) and (\ref{prop_shrinking}), we can partition $[r_j, r_j + \frac{\ell_j}{2}] = [r_j, a] \cup (a,b) \cup [b, r_j + \frac{\ell_j}{2}]$ such that $[r_j, a]$ and $[b, r_j + \frac{\ell_j}{2}]$ are times where $\mathcal{S}$ is running $j$, and $(a,b)$ are times where $\mathcal{S}$ is running descendants of $j$. By taking $\alpha$ sufficiently large, we have $\lvert (a,b) \rvert \leq \frac{\ell_j}{4}$. This follows from Lemma 6 in \cite{KalyanasundaramP03}.
            It follows, at least one of $[r_j, a]$ or $[b, r_j + \frac{\ell_j}{2}]$ has length at least $\frac{\ell_j}{8}$. This gives the desired $I_j$.
        \end{proof}

        Let $\mathcal{S}'' \subset \mathcal{S}$ be the collection of jobs guaranteed by the proposition, so $\lvert \mathcal{S}'' \rvert \geq \frac{1}{2} \lvert \mathcal{S} \rvert$. It suffices to show that $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega(\lvert \mathcal{S}'' \rvert)$. Thus, we argue about $\textsc{MLax}\xspace(J)$ in the interval $I_j$ (guaranteed by \Cref{prop_find_interval}) for some $j \in \mathcal{S}''$.

        \begin{prop}\label{find_srpt_resp}
            Consider any job $j \in \mathcal{S}''$. For sufficiently large $\alpha = O(1)$, $\textsc{MLax}\xspace(J)$ starts running at least $\frac{m}{16}$ jobs during $I_j$ such that each such job $j'$ satisfies $[f_{j'}(\textsc{MLax}\xspace(J)), f_{j'}(\textsc{MLax}\xspace(J)) + x_{j'}] \subset I_j$.
        \end{prop}
        \begin{proof}
            We let $I'$ be the prefix of $I_j$ with length exactly $\frac{\lvert I_j \rvert}{2} \geq \frac{\ell_j}{16}$. Recall that $j \in \mathcal{S}''$ is non-viable. Thus, because $I' \subset I_j \subset [r_j, r_j + \frac{\ell_j}{2}]$, $\textsc{MLax}\xspace(J)$ is always running at least $\frac{1}{8}m$ jobs $j'$ satisfying $\alpha x_{j'} < \ell_j$ during $I'$.

            We define $J'$ to be the set of jobs that $\textsc{MLax}\xspace(J)$ runs during $I'$ satisfying $\alpha x_{j'} < \ell_j$. We further partition $J'$ into size classes, $J' = \bigcup_{z \in \mathbb{N}} J'_z$ such that $J'_z$ consists of the jobs in $J'$ with size in $(\frac{\ell_j}{\alpha^{z+1}}, \frac{\ell_j}{\alpha^z}]$.

            For each machine $i$, we let $T_z^i$ be the times in $I'$ that $\textsc{MLax}\xspace(J)$ is running a job from $J_z'$ on machine $i$. Note that each $T_z^i$ is the union of finitely many intervals. Then because $\textsc{MLax}\xspace(J)$ is always running at least $\frac{1}{8}m$ jobs $j'$ satisfying $\alpha x_{j'} \leq \ell_j$ during $I'$, we have:
            \[\sum_{z \in \mathbb{N}} \sum_{i \in [m]} \lvert T_z^i \rvert \geq \frac{m}{8} \lvert I' \rvert.\]
            By averaging, there exists some $z$ with $\sum_{i \in [m]} \lvert T_z^i \rvert \geq \frac{m}{8} \frac{\lvert I' \rvert}{2^{z+1}}$.

            Fix such a $z$. It suffices to show that there exist at least $\frac{m}{16}$ jobs in $J_z'$ that \textsc{Lax}\xspace~ starts in $I'$. This is because every job $j' \in J_z'$ has size at most $\frac{\ell_j}{\alpha^z}$ and $\lvert I_j \setminus I' \rvert \geq \frac{\ell_j}{16}$. Taking $\alpha \geq 16$ gives that $f_{j'}(\textsc{Lax}\xspace) + x_{j'} \in I_j$.

            Note that every job in $J'_z$ has size within a $\alpha$-factor of each other, so there can be at most one such job per stack at any time. This implies that there are at most $m$ jobs in $J'_z$ that \emph{don't} start in $I'$ (i.e. the start before $I'$.) These jobs contribute at most $m \frac{\ell_j}{\alpha^z}$ to $\sum_{i \in [m]} \lvert T_z^i \rvert$. Choosing $\alpha$ large enough, we can ensure that the jobs in $J'_z$ that start in $I'$ contribute at least $\frac{m}{16} \frac{\ell_j}{\alpha^z}$ to $\sum_{i \in [m]} \lvert T_z^i \rvert$. To conclude, we note that each job in $J_z'$ that starts in $I'$ contributes at most $\frac{\ell_j}{\alpha^z}$ to the same sum, so there must exist at least $\frac{m}{16}$ such jobs.
        \end{proof}

        Using the above proposition, we define a charging scheme to show that $\lvert \textsc{SRPT}\xspace(J) \rvert = \Omega(\lvert \mathcal{S}'' \rvert)$. Each job $j \in \mathcal{S}''$ begins with $1$ credit. By the proposition, we can find $\frac{m}{16}$ jobs $j'$ such that $[f_{j'}(\textsc{MLax}\xspace(J)), f_{j'}(\textsc{MLax}\xspace(J)) + x_{j'}]$ is contained in the time when $\mathcal{S}$ runs $j$. There are two cases to consider. If all $\frac{m}{16}$ jobs we find are contained in $\textsc{SRPT}\xspace(J)$, then we transfer $\frac{16}{m}$ credits from $j$ to each of the $\frac{m}{16}$-many jobs. Note that here we are using $m \geq 16$. Otherwise, there exists some such $j'$ that is not in $\textsc{SRPT}\xspace(J)$. Then $ \textsc{SRPT}\xspace(J)$ will complete at least $m$ jobs in $[f_{j'}(\textsc{MLax}\xspace(J)), f_{j'}(\textsc{MLax}\xspace(J)) + x_{j'}]$. We transfer $\frac{1}{m}$ credits from $j$ to each of the $m$-many jobs. To conclude, we note that each $j' \in \textsc{SRPT}\xspace(J)$ gets $O(\frac{1}{m})$ credits from at most $O(m)$ jobs in $\mathcal{S}''$.
    \end{proof}

\end{proof}

\begin{comment}
    \section{\textsc{SRPT}\xspace is Competitive with the Number of Leaves}
    \label{sect:srptleaves}

    In this section, we observe that the number of jobs completed by \textsc{SRPT}\xspace~ is competitive with the number of leaves  in the optimal forest schedule.
    Intuitively this follows because
    whenever some schedule is running a feasible job, then \textsc{SRPT}\xspace~ either runs the same job or a job with shorter remaining processing time.

    \begin{lem}\label{lem_srpt_leaves}
        Let $\mathcal{S}$ be any forest schedule on $m$ machines that only runs feasible jobs. Let $L$ be the set of leaves of $\mathcal{S}$. Then $\lvert \textsc{SRPT}\xspace \rvert \geq \frac{1}{2} \lvert L \rvert$
    \end{lem}
    \begin{proof}
        It suffices to show that $\lvert L \setminus \textsc{SRPT}\xspace \rvert \leq \lvert \textsc{SRPT}\xspace \rvert$. The main property of \textsc{SRPT}\xspace~ gives:

        \begin{prop}\label{prop_srpt_leaves}
            Consider any leaf $\ell \in L \setminus \textsc{SRPT}\xspace$. Suppose $\mathcal{S}$ starts running $\ell$ at time $t$. Then \textsc{SRPT}\xspace~ completes $m$ jobs in the time interval $[f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$.
        \end{prop}
        \begin{proof}
            At time $f_\ell(\mathcal{S})$ in \textsc{SRPT}\xspace, job $\ell$ has remaining processing time at most $x_\ell$ and is feasible by assumption. Because $\ell \notin \textsc{SRPT}\xspace$, there must exist a first time $t' \in [f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$ where $\ell$ is not run by \textsc{SRPT}\xspace. At this time, \textsc{SRPT}\xspace~ must be running $m$ jobs with remaining processing time at most $x_\ell - (t' - f_\ell(\mathcal{S}))$. In particular, \textsc{SRPT}\xspace~ must complete $m$ jobs by time $f_\ell(\mathcal{S}) + x_\ell$.
        \end{proof}

        Using the proposition, we give a charging scheme: Each job $\ell \in L \setminus \textsc{SRPT}\xspace$ begins with $1$ credit. By the proposition, we can find $m$ jobs that \textsc{SRPT}\xspace~ completes in the time interval $[f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$. Then $\ell$ transfers $\frac{1}{m}$ credits each to $m$ such jobs in \textsc{SRPT}\xspace.

        It remains to show that each $j \in \textsc{SRPT}\xspace$ gets at most $1$ credit. Note that $j$ can only get credits from leaves $\ell$ such that $c_j(\textsc{SRPT}\xspace) \in [f_\ell(\mathcal{S}), f_\ell(\mathcal{S}) + x_\ell]$. There are at most $m$ such intervals (at most one per machine), because we only consider leaves, whose intervals are disjoint if there are on the same machine.
    \end{proof}
\end{comment}

redpajama_set_name: RedPajamaArXiv


When Bill and Mary Moore arrived from Chicago in the 1950s to their new home in Minnesota, they moved into a place rich with the history of the Minnesota River Valley. Here, at the Officer's Quarters of Fort Snelling, an Irish-Catholic Veteran Administrator and his wife raised an enclave of twelve children.
Bill and Mary Moore and their children on front steps of home at Fort Snelling.
One of them, Patrick Moore, found ways to spend plenty of time at the confluence of the Minnesota and Mississippi Rivers as a young boy. Time to traipse through its Oak Savannahs and floodplain forests of Silver Maples and Cottonwoods. Time for curiosity and imagining those who came before him – Native Americans and traders – foraging similar paths. Time to connect with his natural surroundings. It was no surprise, in later years, when Moore chose the direction for his own life that followed this passion: to study history; raise his family near the Minnesota River in charming Montevideo; and organize community to protect and celebrate what he holds close to his heart – the land, water and people of the Minnesota River.
River History Weekend, May, 2012. Chippewa County Park. Wegdahl, Minnesota on the Chippewa River. Isak Kvam, Anna Moore, Patrick Moore, Nikki Liu.
In the early days of the watershed-wide movement to clean up the river, Moore recalls encouraging two delegates in 1992 to join the Citizen's Advisory Committee (CAC), Andrea Myhre, an organizer, and Butch Halterman, a biology teacher in Montevideo. Both were early founders to a new citizen-led group in Montevideo called Clean Up the River Environment (CURE). After reviewing the science of the Minnesota River Assessment Project and recommending how to prioritize cleaning up its polluted waters in the watershed to the state government, they shared their learnings to others in the Montevideo area through CURE.
Biology teacher, Butch Halterman, with his students on an annual Minnesota River paddling and camping excursion.
As a community organizer from 1992 to 1998, Moore facilitated many activities to support CURE's mission to build citizen awareness in the Upper Minnesota River Valley to protect and celebrate the river. These included community events with outdoor recreation and music, river paddle outings, and river clean-ups. CURE also took the lead opposing the straightening of the Lac Qui Parle River by the Army Corps of Engineers in a protracted fight that lasted from 1993 through 1996.
Later, with the support of Dixie Tilden, and encouragement from the Board President Brian Wojtalewicz and Clean Energy consultant, Duane Ninneman, a long, aggressive campaign transpired to advocate against plans to open a second coal-fired power plant, Big Stone II. This plant never opened at the headwaters of the Minnesota River.
In the interim years, when he left CURE to build a coffee shop called Java River, Moore became increasingly aware of the desire in members of his community for more collaboration and alignment and less divisiveness. He noticed that people can't always be fighting against something, they like to work together to show what they are "for." When he returned to CURE as its Executive Director in 2005, Moore sought out activities focused on finding common values, shared identity and passion in the people, which included diverse points of view.
This eventually was reflected in an effort that became known as the Friendship Tour in 2010. Citizens downstream affiliated with the Lake Pepin Legacy Alliance who were concerned about the sediment growth in Lake Pepin joined agricultural leaders upstream to learn about each other's concerns and efforts related to the health of the river.
According to participants like Clarkfield farmer Doug Albin, these efforts helped to diffuse some of the tension between the agriculture community and environmentalists and begin moving the needle towards a climate of more collaborative efforts. This caught the attention of the Bush Foundation, which further supported more dialogue along the basin and community conversations in western Minnesota.
Art of Hosting Training in Granite Falls, MN. May, 2012.
Moore's favorite endeavor, he noted, was helping with the formation of the Minnesota River Watershed Alliance in 2005. This effort also centered around aligning diverse citizens' common passion for the Minnesota River. At a time when the Minnesota River Board of county commissioners was teetering, Moore joined Scott Sparlin of the Coalition for a Clean Minnesota River and Lori Nelson from Friends of the Minnesota Valley, to create a new entity that would represent the passion and voices of the citizens along the entire river basin.
Through this group's ebbs and flows, the passion of the citizens remains the driver of the Minnesota River Watershed Alliance. The members continue to choose one to three key efforts to focus on together each year.
Its current focus is a collaborated effort to nominate the Minnesota River for designation as a National Blueway by the U.S. Department of Interior. Today, this group's membership is wide and growing. It currently includes paddlers, teachers, writers, birders, native american tribes, fishermen, hunters, farmers, soil and water experts, NGOs, people building biking and hiking trails along the river, the U.S. Fish and Wildlife Service, the Department of Natural Resources, research institutions, the Minnesota River Board, and more.
Minnesota River Watershed Alliance meeting, April, 2013. Hutchinson, MN.
Patrick Moore's work has been recognized by many for helping to build community along the Minnesota River. The spirit of celebrating this river continues to grow as does the awareness of each citizen to do his or her part in alignment with this living ecosystem – a system which is in deep need of healing.
To read more about Moore's history on the river, the transcript for this interview is here.
Patrick and all the others that he is working with on these issues are an inspiration to people across the state and beyond, even those of us working in other fields and efforts. Their creativity and passion that has accomplished so much shows the rest of us the way to get things done.
Thanks for doing these interviews.


text:
Home Audi Audi To Be Tottenham Hotspur Football Club's Official Car Partner For Four Years
Audi To Be Tottenham Hotspur Football Club's Official Car Partner For Four Years
August 31, 2018 | Suvil Susvirkar
Added in: Audi
Tottenham Hotspur has (Thursday 16 August 2018) announced Audi as the Club's Official Car Partner in an exclusive four year agreement. Audi will see their brand's iconic four rings feature across digital signage, including the LED advertising system, big screens and the interior TV network at the Club's new stadium, as well as across its digital media channels.
Tottenham Hotspur has become one of the most progressive teams in Europe under Manager Mauricio Pochettino and will be a significant part of the Premier League and Champions League story during the 2018-2019 season. Meanwhile, Audi continues its new product offensive during the same time period, launching a host of cars, including the Q8 luxury SUV, and the e-tron, its first all-electric model.
To mark the beginning of the partnership, players were given a special preview of the Q8 at the Tottenham Hotspur Training Centre, Enfield, before the car's official UK debut.
Mauricio Pochettino, Manager of Tottenham Hotspur (left) with Andrew Doyle, Director of Audi UK (right)
Audi has a long and proud history in football. Tottenham Hotspur is the latest world-famous name to join its portfolio of football partners, which includes German champions Bayern Munich, Spanish champions Barcelona, and European champions Real Madrid.
Fran Jones, Head of Partnerships of Tottenham Hotspur, says: "Audi is a premium brand, so we are delighted to have it on board alongside a number of other leading club partners. We look forward to welcoming Audi and offering them the opportunity to showcase their products across the Club."
Andrew Doyle, Director of Audi UK, says: "The partnership brings two progressive brands together – Audi and Spurs. The Club's legendary Captain Danny Blanchflower famously spoke of 'doing things in style' – this, with our commitment to quality, guides everything we do. Our shared principles of beautiful design and the most advanced technologies further cements our belief that Audi and Spurs will be the perfect marriage."

redpajama_set_name: RedPajamaCommonCrawl


Našli jsme další záznamy k osobě Weldon Sillito.
Weldon Sillito je pohřben(a) na hřbitově Leavitt Cemetery v místě zobrazeném na níže uvedené mapě. Tyto informace o GPS jsou k dispozici POUZE na stránkách BillionGraves. Naše technologie vám pomůže najít umístění hrobu a také další členy rodiny, pohřbené poblíž.
Weldon Sillito was 19 years old when Adolf Hitler signs an order to begin the systematic euthanasia of mentally ill and disabled people. Adolf Hitler was a German politician, demagogue, and Pan-German revolutionary, who was the leader of the Nazi Party, Chancellor of Germany from 1933 to 1945 and Führer ("Leader") of Nazi Germany from 1934 to 1945. As dictator, Hitler initiated World War II in Europe with the invasion of Poland in September 1939, and was central to the Holocaust.
Weldon Sillito was 21 years old when World War II: The Imperial Japanese Navy made a surprise attack on Pearl Harbor in Hawaii, intending to neutralize the United States Pacific Fleet from influencing the war Japan was planning to wage in Southeast Asia. World War II, also known as the Second World War, was a global war that lasted from 1939 to 1945, although conflicts reflecting the ideological clash between what would become the Allied and Axis blocs began earlier. The vast majority of the world's countries—including all of the great powers—eventually formed two opposing military alliances: the Allies and the Axis. It was the most global war in history; it directly involved more than 100 million people from over 30 countries. In a state of total war, the major participants threw their entire economic, industrial, and scientific capabilities behind the war effort, blurring the distinction between civilian and military resources. World War II was the deadliest conflict in human history, marked by 50 to 85 million fatalities, most of whom were civilians in the Soviet Union and China. It included massacres, the genocide of the Holocaust, strategic bombing, premeditated death from starvation and disease and the only use of nuclear weapons in war.
Weldon Sillito was 32 years old when Jonas Salk announced the successful test of his polio vaccine on a small group of adults and children (vaccination pictured). Jonas Edward Salk was an American medical researcher and virologist. He discovered and developed one of the first successful polio vaccines. Born in New York City, he attended New York University School of Medicine, later choosing to do medical research instead of becoming a practicing physician. In 1939, after earning his medical degree, Salk began an internship as a physician scientist at Mount Sinai Hospital. Two years later he was granted a fellowship at the University of Michigan, where he would study flu viruses with his mentor Thomas Francis, Jr.
Weldon Sillito was 44 years old when Martin Luther King Jr. received the Nobel Peace Prize for combating racial inequality through nonviolence. Martin Luther King Jr. was an American Baptist minister and activist who became the most visible spokesperson and leader in the civil rights movement from 1954 until his death in 1968. Born in Atlanta, King is best known for advancing civil rights through nonviolence and civil disobedience, tactics his Christian beliefs and the nonviolent activism of Mahatma Gandhi helped inspire.
Weldon Sillito was 56 years old when Star Wars is released in theaters. Star Wars is a 1977 American epic space opera film written and directed by George Lucas. It is the first film in the original Star Wars trilogy and the beginning of the Star Wars franchise. Starring Mark Hamill, Harrison Ford, Carrie Fisher, Peter Cushing, Alec Guinness, David Prowse, James Earl Jones, Anthony Daniels, Kenny Baker, and Peter Mayhew, the film focuses on the Rebel Alliance, led by Princess Leia (Fisher), and its attempt to destroy the Galactic Empire's space station, the Death Star.
Weldon Sillito was 59 years old when Mount St. Helens erupts in Washington, United States, killing 57 people and causing $3 billion in damage. Mount St. Helens or Louwala-Clough is an active stratovolcano located in Skamania County, Washington, in the Pacific Northwest region of the United States. It is 50 miles (80 km) northeast of Portland, Oregon and 96 miles (154 km) south of Seattle, Washington. Mount St. Helens takes its English name from the British diplomat Lord St Helens, a friend of explorer George Vancouver who made a survey of the area in the late 18th century. The volcano is located in the Cascade Range and is part of the Cascade Volcanic Arc, a segment of the Pacific Ring of Fire that includes over 160 active volcanoes. This volcano is well known for its ash explosions and pyroclastic flows.
Weldon Sillito was 71 years old when The World Wide Web is opened to the public. The World Wide Web (WWW), also called the Web, is an information space where documents and other web resources are identified by Uniform Resource Locators (URLs), interlinked by hypertext links, and accessible via the Internet. English scientist Tim Berners-Lee invented the World Wide Web in 1989. He wrote the first web browser in 1990 while employed at CERN in Switzerland. The browser was released outside CERN in 1991, first to other research institutions starting in January 1991 and to the general public on the Internet in August 1991.
Weldon Sillito was 81 years old when The September 11 attacks, a series of coordinated suicide attacks killing 2,996 people using four aircraft hijacked by 19 members of al-Qaeda. Two aircraft crash into the World Trade Center in New York City, a third crashes into The Pentagon in Arlington County, Virginia, and a fourth into a field near Shanksville, Pennsylvania. The September 11 attacks were a series of four coordinated terrorist attacks by the Islamic terrorist group al-Qaeda against the United States on the morning of Tuesday, September 11, 2001. The attacks killed 2,996 people, injured over 6,000 others, and caused at least $10 billion in infrastructure and property damage. Additional people died of 9/11-related cancer and respiratory diseases in the months and years following the attacks.


42" Cylindrical Scrub Brushes for Power Boss Combination Sweeper and Scrubber Models 9082.
Available in 65/46 Grit, 35/180 Grit, Stiff Poly, and Nylon. These replacement brushes are designed to identically replace your existing Power Boss Combination Sweeper/Scrubber Machine brushe model 9090 Series Double Cylindrical Brush Scrubber at a significant savings to you without sacrificing the quality you require.
If you do not find your model number on our website, call our customer service office 1-800-645-4111 8am-4:30pm EST, and we will be happy to assist you. When ordering online, please specify your model in the customer notes when checking out.