Computer Science Institute of Charles Univ., Faculty of Mathematics and
Physics, Prague, Czechia<EMAIL_ADDRESS>Computer Science Institute of
Charles Univ., Faculty of Mathematics and Physics, Prague, Czechia
<EMAIL_ADDRESS>https://orcid.org/0000-0003-3658-4848 Josef Minařík and
Jiří Sgall [500]Theory of computation Online algorithms [500]Theory of
computation Scheduling algorithms Partially supported by grant 24-10306S of GA
ČR. Amit Kumar and Noga Ron-Zewi 2 Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
APPROX/RANDOM 2024 APPROX/RANDOM 2024 August 28–30, 2024 London School of
Economics, London, UK 317 8

# Speed-robust scheduling revisited

Josef Minařík  Jiří Sgall

###### Abstract

Speed-robust scheduling is the following two-stage problem of scheduling $n$
jobs on $m$ uniformly related machines. In the first stage, the algorithm
receives the value of $m$ and the processing times of $n$ jobs; it has to
partition the jobs into $b$ groups called bags. In the second stage, the
machine speeds are revealed and the bags are assigned to the machines, i.e.,
the algorithm produces a schedule where all the jobs in the same bag are
assigned to the same machine. The objective is to minimize the makespan (the
length of the schedule). The algorithm is compared to the optimal schedule and
it is called $\rho$-robust, if its makespan is always at most $\rho$ times the
optimal one.

Our main result is an improved bound for equal-size jobs for $b=m$. We give an
upper bound of $1.6$. This improves previous bound of $1.8$ and it is almost
tight in the light of previous lower bound of $1.58$. Second, for
infinitesimally small jobs, we give tight upper and lower bounds for the case
when $b\geq m$. This generalizes and simplifies the previous bounds for $b=m$.
Finally, we introduce a new special case with relatively small jobs for which
we give an algorithm whose robustness is close to that of infinitesimal jobs
and thus gives better than $2$-robust for a large class of inputs.

###### keywords:

scheduling, approximation algorithms, makespan, uniform speeds

##  1 Introduction

Speed-robust scheduling is a two-stage problem that was introduced by Eberle
et al. [4]. The eventual goal is to schedule on $m$ uniformly related
machines, however their speeds are not known at the beginning. In the first
stage, the algorithm receives the value of $m$ and the processing times of $n$
jobs; it has to partition the jobs into $b$ groups called bags. In the second
stage, the machine speeds are revealed and the bags are assigned to the
machines, i.e., the algorithm produces a schedule where all the jobs in the
same bag are assigned to the same machine. The objective is to minimize the
makespan (the length of the schedule). The algorithm is compared to the
optimal schedule of the jobs on the machines with known speeds; it is called
$\rho$-robust, if its makespan is always at most $\rho$ times the optimal one.

This problem is motivated by situations like the following one. Suppose that
you have $n$ computational tasks that you want to solve. You have a
computational cluster available, but with unknown parameters. You only know
that there will be (at most) $m$ machines available on the cluster. You do not
know anything about the performance of the machines—some of the machines might
be faster than others; you only know that there will be (at most) $m$ machines
available on the cluster. Furthermore, you can submit at most $b$ different
tasks to the cluster. Hence you will have to partition your $n$ tasks into at
most $b$ groups. One such group will then have to be executed on one machine.
The cluster will then schedule the groups optimally, knowing the speeds of the
machines, and minimize the makespan.

Studying uncertainty in scheduling has a long history. In the classical online
scheduling [9], the machine environment is usually fixed and the uncertainty
stems from job arrivals. Considering uncertainty in the machine environment is
less frequent. One early example is the work of Csanád and Noga [7], where
additional machines can be bought for a certain cost. A substantial body of
research with changing machine speeds is the area of dynamic speed scaling, in
particular in the context of minimizing the power consumption, see [1, 8];
however, note that here the changing speeds are not a part of the adversarial
environment but used by the algorithm to its advantage. Another direction
considers online scheduling with unavailability periods [3]. One-machine
scheduling with adversarially changing machine speed was considered in [5] in
the context of unreliable machines.

Completely reversing the scenario with all jobs known from the beginning but
uncertain machine environment is a recent new model introduced by Stein and
Zhong [10] and Eberle et al. [4], see Section 1.2.

###  1.1 Formal definitions

Formally, in the first stage, we receive three positive integers $n,m,b$ and
$n$ non-negative real numbers $p_{1},\ldots,p_{n}$ representing the processing
times of $n$ jobs. The total processing time is denoted
$P=\sum_{j=1}^{m}p_{j}$. The output of our first-stage algorithm is a mapping
$B:\\{1,\ldots,n\\}\to\\{1,\ldots,b\\}$, where $B(j)=i$ represents the fact
that the job $j$ was assigned to the bag $i$. The sum of the processing times
of all the jobs assigned to bag $i$ the size of bag $i$ and denoted
$a_{i}=\sum_{j:B(j)=i}p_{j}$. The exact mapping $B$ is not important for the
second stage since the makespan depends only on the bag sizes.

In the second stage, we are given the bag sizes $a_{1},\ldots,a_{b}$ and the
previously unknown machine speeds $s_{1},\ldots,s_{m}\geq 0$, not all equal to
$0$. We partition the bag indices $\\{1,\ldots,b\\}$ into $m$ sets $M_{1}$, …,
$M_{m}$, representing the assignment to the $m$ machines. Machine $i$ then has
a completion time $C_{i}=(\sum_{j\in M_{i}}a_{j})/s_{i}$; for $s_{i}=0$ we
require $M_{i}=\emptyset$ and set $C_{i}=0$, i.e., machine of speed $0$ does
not accept any jobs. Finally, $C_{\max}=\max_{i=1}^{m}C_{i}$ is the makespan,
i.e., the length of the schedule.

Let $C_{\max}^{*}$ denote the makespan of the adversary, who does not have to
create bags and can assign jobs directly to machines. Alternatively and
equivalently, the adversary also creates bags, but with the knowledge of the
speeds already in the first stage.

We call a first stage algorithm $\rho$-robust if, for all possible inputs and
for all possible choices of machine speeds, there exists a second-stage
assignment of bags to machines such that $C_{\max}\leq\rho\cdot C_{\max}^{*}$.
Intuitively, an algorithm is $\rho$-robust if it performs at most $\rho$ times
worse than the adversary.

The previous definition implicitly assumes that the second stage is solved
optimally. This is reasonable, as the scheduling on uniformly related machines
allows PTAS, see [6, 11], so the chosen (presumably optimal) second-stage
solution can be replaced by an arbitrarily good approximation. Also, our
proofs show that the second-stage algorithm can be implemented by efficient
greedy algorithms without any loss of performance, once the optimal makespan
or its approximation is known.

We call the special cases of the problem sand, bricks, rocks and pebbles.
Sand, bricks, and rocks were introduced by Eberle et al. [4]. These words
represent the types of jobs.

  * •

Rocks can be any shape or size and represent jobs of arbitrary processing
time. This is the most general setting.

  * •

Bricks are all the same and represent jobs with equal processing times.

  * •

Sand grains are very small and represent infinitesimally small processing
times.

  * •

Pebbles represent jobs that are relatively small compared to the average load
of all machines. We call an instance of speed-robust scheduling $q$-pebbles if
$p_{j}\leq q\cdot\frac{P}{m}$ holds for all jobs $j$.

###  1.2 Previous results

The two-stage scheduling problem with uncertainty in the machine environment
was introduced by Stein and Zhong [10]. They focused on the case of $m$
identical machines where in the second stage some machine might fail and then
do not process any tasks. This amounts to a special case of speed-robust
scheduling where $s_{i}\in\\{0,1\\}$ for $1\leq i\leq m$. They gave lower
bounds of $4/3$ for equal-size jobs (bricks) and $(\sqrt{2}+1)/2\approx 1.207$
for infinitesimal jobs (sand). Their algorithms were later improved by Eberle
et al. [4] to algorithms matching the lower bounds in both cases.

Our immediate predecessor, Eberle et al. [4], introduced the speed-robust
scheduling for general speeds, i.e., on uniformly related machines. They
studied mainly the case $b=m$, i.e., the case when the number of bags is equal
to the number of machines. For this case they gave tight bounds for sand for
every $m$, for large $m$ the bound approaches $e/(e-1)\approx 1.58$. For
equal-size jobs (bricks), they have shown an upper bound of $1.8$.

For the most general case of rocks, the strongest known result is the
algorithm with the robustness factor at most $1+(m-1)/b$, which equals $2-1/m$
for $b=m$, given also by Eberle et al. [4]. It remains an interesting open
problem to improve this bound, in particular to give an upper bound
$2-\varepsilon$ for rocks and $b=m$.

###  1.3 Our results

We now describe our results and compare them to the previous ones in each of
the scenarios.

#### Sand.

For sand, we give matching lower and upper bounds for any $b$ and $m$. Namely,
for $b\geq m$ we give an optimal algorithm which is
$\overline{\rho}(m,b)$-robust for

$\overline{\rho}(m,b)=\frac{m^{b}}{m^{b}-(m-1)^{b}}=\frac{1}{1-\left(1-\frac{1}{m}\right)^{b}}\,.$
(1.1)

This matches the results of Eberle et al. [4] who gave an algorithm with the
robustness factor equal to $\overline{\rho}(m,b)\leq e/(e-1)\approx 1.58$ for
$b=m$, generalizes them to arbitrary $b\geq m$ and significantly simplifies
the proof.

An interesting case is when the number of bags is a constant multiple of $m$.
For a fixed $\alpha\geq 1$ and $b=\alpha m$, our bound approaches
$1/(1-e^{-\alpha})$ from below for a large $m$. For example, doubling the
number of bags to $b=2m$ decreases the robustness factor from $1.58$ to
$1.16$.

If $b<m$, the second-stage algorithm uses only the $b$ fastest machines, so we
can decrease $m$ to $m^{\prime}=b$ and tight results with robustness factor
$\overline{\rho}(m^{\prime},b)=\overline{\rho}(b,b)$ follow already from [4].

#### Pebbles.

For the new case of $q$-pebbles and $b\geq m$, we give a
$(\overline{\rho}(m,b)+q)$-robust algorithm. For $p<0.42$, this gives an
algorithm with the robustness factor below $2$, i.e., below the currently
strongest known upper bound for rocks.

#### Bricks.

As our main result, we give a $1.6$-robust algorithm for bricks for $b=m$.
This improves the bound of $1.8$ from Eberle et al. [4].

Furthermore, as a direct application of our results for pebbles we give a
$(\overline{\rho}(m,b)+m/n)$-robust algorithm for any $n$ and $b\geq m$. This
improves and generalizes the $((1+m/n)\overline{\rho}(m,m))$-robust algorithm
for $b=m$ given by Eberle et al. [4]. Namely, we improve the multiplicative
factor of $(1+m/n)$ to only an additive term of $m/n$.

#### Structure of the paper.

We give some general preliminaries in Section 2. We give the results for sand
and pebbles in Sections 3 and 4. We focus on our main result for bricks in
Section 5. Some small cases need computer verification or tabulation of
parameters, results of these are given in Appendix A.

##  2 Preliminaries

We assume that the processing times, the machine speeds, and the bag sizes are
always listed in a non-increasing order.

In the rest of this paper, we will make two assumptions below that restrict
the speeds to particular special cases. This is without loss of generality,
leveraging the fact that the algorithm must commit the bag sizes in the first
phase without knowing the speeds.

  * •

The optimal makespan is equal to 1. This implies that the robustness factor is
equal to the makespan of the algorithm.

Scaling all the speeds does not change the ratio of the makespans of our
algorithm and the adversary. Thus for every instance of the problem, there
exists another instance with $C^{*}_{\max}=1$ that differs only in the speeds
and the ratio of makespans of our algorithm and the adversary remains the
same. It follows that any first-stage algorithm that is $\rho$-robust for
instances with $C^{*}_{\max}=1$ is $\rho$-robust for general instances, too.

  * •

The sum of the processing times of all jobs equals to the sum of the speeds of
all the machines, i.e., $P=\sum_{i=1}^{m}p_{i}=\sum_{i=1}^{m}s_{i}$. In other
words, the adversary is fully utilizing all the machines, and the completion
time of all the machines with non-zero speed is equal to 1, using the previous
assumption.

If there is some machine $i$ with $s_{i}>0$ and completion time $C^{*}_{i}<1$
in the optimal schedule, we change its speed to
$s^{\prime}_{i}=C^{*}_{i}s_{i}$. This does not change the optimal makespan of
the adversary and the makespan of the algorithm can only increase. Once again,
it follows that any first-stage algorithm that is $\rho$-robust for these
special instances is also $\rho$-robust for general instances.

For the second stage, typically, we use a simple greedy algorithm for the
second stage instead of analyzing the optimal schedule. Technically, for an
algorithm we need to know the optimal makespan (to modify the speeds
appropriately, according to the assumptions above). However note that first we
can approximate the makespan and second the algorithm is only used as a tool
in the analysis.

For sand and pebbles we use Algorithm GreedyAssignment (see below), a variant
of the well-known LPT algorithm. It is parameterized by $\rho$, the robustness
factor to be achieved. At the beginning, every machine is assigned a capacity
equal to its speed multiplied by $\rho$. The algorithm then goes through all
the bags from large to small, assigns them on the machine with the largest
capacity remaining, and decreases the capacity appropriately. If the
capacities remain non-negative at the end, the makespan of the created
assignment is at most $\rho$ since machine $i$ has been assigned jobs of total
processing times at most $\rho s_{i}$.

Algorithm GreedyAssignment

Input: bag sizes $a_{1}\geq\cdots\geq a_{b}$; machine speeds
$s_{1}\geq\cdots\geq s_{m}$; desired robustness factor $\rho$

for $i\leftarrow 1$ to $m$ do

$c_{i}\leftarrow\rho s_{i}$ $\triangleright$ Initialize the capacities of all
machines

$M_{i}=\emptyset$ $\triangleright$ Initialize the assignment

for $k\leftarrow 1$ to $b$ do

$i\leftarrow$ index of a machine with the largest $c_{i}$

$M_{i}\leftarrow M_{i}\cup\\{k\\}$ $\triangleright$ Assign bag $k$ to machine
$i$

$c_{i}\leftarrow c_{i}-a_{k}$ $\triangleright$ Decrease the remaining capacity
of the selected machine

return $M_{1},\ldots,M_{m}$

We use this to formulate the following sufficient condition for
$\rho$-robustness of an algorithm which is instrumental in proving the upper
bounds for sand and pebbles.

######  Theorem 2.1.

If a first-stage algorithm always produces bag sizes satisfying inequalities
$\displaystyle a_{k}\leq\frac{\rho P-\sum_{j=1}^{k-1}a_{j}}{m}\,,$ for all
$k=1,\ldots,b$, then the algorithm is $\rho$-robust.

######  Proof 2.2.

Recall that we assume $\sum_{i=1}^{m}s_{i}=P$. We claim that the second-stage
algorithm GreedyAssignment produces an assignment with makespan at most
$\rho$. We only need to show that there is a machine with capacity at least
$a_{k}$ when assigning the $k$th bag. The initial total capacity was $\rho P$
and was already decreased by $\sum_{j=1}^{k-1}a_{j}$ at the time of assigning
bag $a_{k}$. It follows that the remaining capacity is equal to $\rho
P-\sum_{j=1}^{k-1}a_{j}$ and thus there exists a machine with capacity at
least $(\rho P-\sum_{j=1}^{k-1}a_{j})/m\geq a_{k}$.

##  3 Sand

Intuitively, the case of sand corresponds to the limit case where $n$ is large
and all the jobs are small and have equal sizes. One can view this as an
infinite number of infinitesimal jobs.

More formally, we are given just $m$, $b$, and $P$ as an input of the first
stage. The result of the first stage are $b$ non-negative reals
$a_{1},\ldots,a_{b}$ whose sum equals $P$. The formulation of the second stage
remains the same.

The model of infinitesimally small jobs resembles preemptive scheduling. In
the optimal algorithm for preemptive scheduling [2], one needs to maintain the
loads of machines in a geometric sequence with common ratio $m/(m-1)$ for $m$
machines, roughly speaking. The proofs for sand show that here the same
geometric sequence is also crucial, in particular it is used for the bag sizes
in the algorithm. We now describe the sequence and state its properties useful
both for the upper and lower bounds.

We define $U=m^{b}$, $L=m^{b}-(m-1)^{b}$ and $t_{j}=m^{b-j}(m-1)^{j-1}$ for
$j\in\\{1,\ldots,b\\}$.

Observe that equation (1.1) defines $\overline{\rho}$ as
$\overline{\rho}(m,b)=U/L$.

######  Lemma 3.1.

For all $k=1,\ldots,b$, it holds that $\sum_{j=1}^{k}t_{j}=U-(m-1)t_{k}$. In
particular, $\sum_{j=1}^{b}t_{j}=U-(m-1)^{b}=L$.

######  Proof 3.2.

We proceed by induction on $k$. The lemma holds for $k=1$ since $U=mt_{1}$ and
thus $t_{1}=U-(m-1)t_{1}$. Now suppose it holds for $k$. We can derive

$\sum_{j=1}^{k+1}t_{j}=U-(m-1)t_{k}+t_{k+1}=U-m^{b-k}(m-1)^{k}+m^{b-k-1}(m-1)^{k}=U-(m-1)t_{k+1}$

which completes the induction step.

Figure 3.1: An example of bag sizes chosen for $m=2$ and $b=4$.

To get some intuition behind the algorithm for sand, it might be useful to
consider the case $m=2$, see Figure 3.1. Suppose that $P=L=2^{b}-1$, choose
the bag sizes $a_{k}=t_{k}=2^{b-k}$. For $m=2$ the sizes are powers of two, so
it is easy to see that we can achieve the robustness ratio of
$1+1/(2^{b}-1)=2^{b}/(2^{b}-1)$ as follows: The adversary chooses any speeds
$s_{1},s_{2}$ such that $s_{1}+s_{2}=P=2^{b}-1$. The capacities of the
machines (as in GreedyAssignment) then satisfy $c_{1}+c_{2}=2^{b}$ and thus
$\lfloor c_{1}\rfloor+\lfloor c_{2}\rfloor\geq 2^{b}-1$. We can express
$\lfloor c_{1}\rfloor$ in binary, assign the corresponding bags on the first
machine and the remaining bags to the second machine.

###  3.1 Upper bound

We use a different approach than Eberle et al. [4] for the proof of the upper
bound. We choose the same bag sizes (for $b=m$) but we simplify the proof by
use of Theorem 2.1. Algorithm Sand describes the bag sizes. Note that the sum
of bag sizes produced by Sand is $P$, using Lemma 3.1.

Algorithm Sand

Input: number of bags $b$; number of machines $m$; total amount of sand $P$

$L\leftarrow m^{b}-(m-1)^{b}$

for $j\leftarrow 1$ to $b$ do $a_{j}\leftarrow t_{j}\frac{P}{L}$

return $a_{1},a_{2},\ldots,a_{b}$

######  Theorem 3.3.

Algorithm Sand is $\overline{\rho}(m,b)$-robust for sand, for
$\overline{\rho}$ defined by (1.1).

######  Proof 3.4.

We assume $P=L$ since it does not change the ratio of our makespan and the
makespan of the adversary. Under this assumption, Sand produces bag sizes
$a_{k}=t_{k}$.

It is sufficient to show that the bag sizes produced by Sand satisfy the
condition of Theorem 2.1. Let us prove the $k$th inequality in the assumption
of the theorem. We have

$\overline{\rho}(m,b)P-\sum_{j=1}^{k-1}a_{j}=\frac{U}{L}L-\sum_{j=1}^{k-1}t_{j}=U-\sum_{j=1}^{k}t_{j}+t_{k}\,.$

According to Lemma 3.1, we can simplify the right-hand side as follows.

$U-\sum_{j=1}^{k}t_{j}+t_{k}=U-(U-(m-1)t_{k})+t_{k}=mt_{k}=ma_{k}\,.$

The $k$th inequality in the assumption of Theorem 2.1 follows, in fact it
holds with equality.

Theorem 2.1 now implies that there exists an assignment with makespan at most
$\overline{\rho}(m,b)$.

###  3.2 Lower bound

The following proof is a slightly modified and generalized version of the
proof by Eberle et al. [4]. The main difference is that we do not require the
number of bags and machines to be the same.

######  Theorem 3.5.

No deterministic algorithm for sand may have a robustness factor smaller than
$\overline{\rho}(m,b)$, for $\overline{\rho}$ defined by (1.1).

######  Proof 3.6.

Let us without loss of generality assume $P=U$ (be aware that we assumed $P=L$
in the proof of the upper bound). Let us denote the chosen bag sizes by
$a_{1}\geq\cdots\geq a_{b}$. We will restrict the adversary to $b$ different
speed configurations indexed by $k$, where

$\mathcal{S}_{k}=\\{s_{1}=U-(m-1)t_{k},\leavevmode\nobreak\
s_{2}=t_{k},\leavevmode\nobreak\ s_{3}=t_{k},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\ s_{m}=t_{k}\\}\,.$

See Figure 3.2 for an example. Note that the sum of machine speeds is equal to
$U$ in every configuration and hence the makespan of the adversary is indeed 1
as we always assume. In every speed configuration, there are $m-1$ slow
machines and one fast machine, since

$s_{1}=U-(m-1)t_{k}=\sum_{j=1}^{k}t_{j}\geq t_{k}\,.$

Figure 3.2: An example of speed configurations considered by the adversary for
$m=2$ and $b=4$.

Let $k_{\max}$ be the largest index such that
$a_{k_{\max}}\geq\frac{U}{L}t_{k_{\max}}$. This index must exist since

$\sum_{j=1}^{b}a_{j}=U=\frac{U}{L}L=\frac{U}{L}\sum_{j=1}^{b}t_{j}\,.$

Now let the adversary choose the speed configuration $\mathcal{S}_{k_{\max}}$.
We distinguish two cases depending on the bag assignment in the second stage.

Case 1: At least one of the bags $a_{1},\ldots,a_{k_{\max}}$ is assigned to a
slow machine. The makespan is at least the completion time of this machine
which is at least

$\frac{a_{j}}{t_{k_{\max}}}\geq\frac{a_{k_{\max}}}{t_{k_{\max}}}\geq\frac{U}{L}\,.$

Case 2: All of the bags $a_{1},\ldots,a_{k_{\max}}$ are assigned to the fast
machine. Total size of the bags assigned to the fast machine is at least

$\sum_{j=1}^{k_{\max}}a_{j}=U-\sum_{j=k_{\max}+1}^{b}a_{j}\,.$

By definition of $k_{\max}$ it holds that $a_{j}<\frac{U}{L}t_{j}$ for
$j>k_{\max}$ and we can bound

$U-\sum_{j=k_{\max}+1}^{b}a_{j}\geq
U-\frac{U}{L}\sum_{j=k_{\max}+1}^{b}t_{j}\,.$

Since $\sum_{j=1}^{b}t_{j}=L$, we can rearrange the right-hand side as follows

$U-\frac{U}{L}\sum_{j=k_{\max}+1}^{b}t_{j}=U-\frac{U}{L}\left(L-\sum_{j=1}^{k_{\max}}t_{j}\right)=\frac{U}{L}\sum_{j=1}^{k_{\max}}t_{j}\,.$

By Lemma 3.1 it holds that

$\frac{U}{L}\sum_{j=1}^{k_{\max}}t_{j}=\frac{U}{L}\left(U-(m-1)t_{k_{\max}}\right)=\frac{U}{L}s_{1}$

due to the choice of $s_{1}$ in the configuration $\mathcal{S}_{k_{\max}}$.
Thus the makespan would be at least $U/L=\overline{\rho}(m,b)$.

The makespan was at least $U/L$ in both cases, hence the robustness factor is
at least $U/L=\overline{\rho}(m,b)$ and the theorem follows.

##  4 Pebbles

Recall that an instance of our problem is called $q$-pebbles if the processing
times satisfy

$p_{j}\leq q\cdot\frac{P}{m}=q\cdot\frac{\sum_{\ell=1}^{n}p_{\ell}}{m}\,.$

This definition might seem a bit unnatural at the first glance, but there is a
very intuitive formulation. The expression $\frac{P}{m}$ represents the
average load of a machine. The definition of pebbles says that the processing
times are relatively small compared to the average load of all machines.

Without loss of generality we assume in this section that the sum of
processing times is $P=m$. This transforms the condition for $q$-pebbles from
the definition into

$p_{j}\leq q\,,$

which is easy to work with.

We use similar ideas as in the optimal algorithm for sand. Recall the
condition of Theorem 2.1

$a_{k}\leq\frac{\rho P-\sum_{j=1}^{k-1}a_{j}}{m}\,.$

As we have already noticed in Section 3.1, the optimal bag sizes for sand not
only satisfy the above inequality, they actually have equality there. The bag
sizes for sand are given by the recurrence

$a_{k}=\frac{\overline{\rho}(m,b)P-\sum_{j=1}^{k-1}a_{j}}{m}\,.$

When we in addition assume $P=m$, as in the case of pebbles, we get

$a_{k}=\overline{\rho}(m,b)-\frac{1}{m}\sum_{j=1}^{k-1}a_{j}.$ (4.1)

Let $a_{1},\ldots,a_{b}$ denote values given by the recurrence (4.1) for the
rest of this section. Remember that the sum of $a_{1},\ldots,a_{b}$ equals
$P$. Let us denote the bag sizes we will be choosing for pebbles
$d_{1},\ldots,d_{b}$. We again want to use Theorem 2.1. In other words, for
the desired robustness factor $\rho$, we want the bag sizes to satisfy

$d_{k}\leq\rho-\frac{1}{m}\sum_{j=1}^{k-1}d_{j}\,.$ (4.2)

Consider the following algorithm. Place as many pebbles as you can into the
first bag while it satisfies the inequality (4.2). Then do the same for the
second bag and so on until the last bag (or until we run out of jobs). See
Pebbles for pseudocode.

Algorithm Pebbles

Input: processing times $p_{1}\geq\cdots\geq p_{m}$; number of machines $m$;
number of bags $b$; desired robustness factor $\rho$

$B\leftarrow$ empty mapping

for $k\leftarrow 1$ to $b$ do $d_{k}\leftarrow 0$ $\triangleright$ $d_{k}$
represents the size of the $k$th bag

$k\leftarrow$ 1 $\triangleright$ $k$ represents index of currently considered
bag

for $j\leftarrow 1$ to $n$ do

while $k\leq b$ and $d_{k}+p_{j}>\rho-\frac{1}{m}\sum_{\ell=1}^{k-1}d_{\ell}$
do $k\leftarrow k+1$

if $k>b$ then break

$B[j]\leftarrow k$

$d_{k}\leftarrow d_{k}+p_{j}$

return $B$

######  Theorem 4.1.

There exists a $(\overline{\rho}(m,b)+q)$-robust algorithm for $q$-pebbles,
for $\overline{\rho}$ defined by (1.1).

######  Proof 4.2.

We show that Algorithm Pebbles puts every job in some bag for
$\rho=\overline{\rho}(m,b)+q$.

Suppose for a contradiction that the algorithm does not use all the jobs. Then
the bag sizes $d_{k}$ at the end of the algorithm must satisfy

$d_{k}+q>\rho-\frac{1}{m}\sum_{j=1}^{k-1}d_{j}\,.$

Indeed, if for some $k$ this inequality is not satisfied, adding one more job
of size at most $p$ to bag $k$ would not violate the inequality (4.2) and the
algorithm would have done so.

Plugging in the expression for $\rho$ gives us

$d_{k}>\overline{\rho}(m,b)-\frac{1}{m}\sum_{j=1}^{k-1}d_{j}.$ (4.3)

We are going to show

$\sum_{j=1}^{k}d_{j}\geq\sum_{j=1}^{k}a_{j}\,,$ (4.4)

for all $k\in\\{0,\ldots,b\\}$. We prove this claim by induction. The case
$k=0$ is trivial since the summations are empty and both sides are equal to 0.
Let us now prove the induction step for $k$ using the equation (4.1) and the
inequality (4.3).

$d_{k}-a_{k}\geq\left(\overline{\rho}(m,b)-\frac{1}{m}\sum_{j=1}^{k-1}d_{j}\right)-\left(\overline{\rho}(m,b)-\frac{1}{m}\sum_{j=1}^{k-1}a_{j}\right)=-\frac{1}{m}\left(\sum_{j=1}^{k-1}d_{j}-\sum_{j=1}^{k-1}a_{j}\right)$

We can now easily finish the induction step. We simplify

$\displaystyle\sum_{j=1}^{k}d_{j}$
$\displaystyle-\sum_{j=1}^{k}a_{j}=\left(\sum_{j=1}^{k-1}d_{j}-\sum_{j=1}^{k-1}a_{j}\right)+\left(d_{k}-a_{k}\right)$
$\displaystyle\geq\left(\sum_{j=1}^{k-1}d_{j}-\sum_{j=1}^{k-1}a_{j}\right)-\frac{1}{m}\left(\sum_{j=1}^{k-1}d_{j}-\sum_{j=1}^{k-1}a_{j}\right)=\frac{m-1}{m}\left(\sum_{j=1}^{k-1}d_{j}-\sum_{j=1}^{k-1}a_{j}\right),$

which is non-negative by the induction hypothesis for $k-1$ and thus the claim
(4.4) holds.

Using the claim (4.4) for $k=b$ gives us

$\sum_{j=1}^{b}d_{j}\geq\sum_{j=1}^{b}a_{j}=P\,,$

which is a contradiction with the assumption that we did not use all jobs.

It is interesting to take a look at the case $b=m$. Theorem 4.1 implies that
there exists an algorithm with robustness factor at most

$\frac{e}{e-1}+q\approx 1.58+q\,.$

The best know result for rocks gives robustness factor $2-1/m$. This gets
arbitrarily close to 2 for large $m$. Hence we have obtained a stronger result
for

$q<2-\frac{e}{e-1}\approx 0.42\,.$

##  5 Bricks

In this section, we study the case of jobs with equal processing times. An
important parameter is the ratio of the number of jobs and the number of
machines, which we denote $\lambda=n/m$. We can scale the instance so that
$p_{j}=1$ for all $j$, which we assume from now on. Note that now $P=n$ and
the average load is $P/m=n/m=\lambda$.

Thus the instance satisfies the definition of $p$-pebbles for $p=1/\lambda$.
Theorem 4.1 immediately implies our first improved bound for bricks:

######  Theorem 5.1.

There exists an algorithm with robustness factor at most
$\overline{\rho}(b,m)+m/n$ solving the problem for $n$ bricks, $m$ machines
and $b$ bags. ∎

In the rest of this section we focus on our main result, the $1.6$-robust
algorithm for bricks in case $b=m$. This will have the following ingredients:

  * •

For $\lambda\geq 60$ we have $e/(e-1)+1/60<1.6$, so by Theorem 5.1 we can use
Algorithm Pebbles.

  * •

For $\lambda<60$ we design a new algorithm Bricks. We split the analysis into
two cases.

    * –

For $m\geq 144$, we modify its solution into a certain fractional solution,
which is easier to analyze, and bound the difference between the two
solutions.

    * –

For $m<144$, we have a finite number of instances, which we verify using a
computer.

We stress that the analysis of instances for $m<144$ shows that Algorithm
Bricks works here without any changes, too, i.e., it does not lead to an
algorithm with exploding number of cases tailored to specific inputs.

###  5.1 First stage algorithm Bricks

Our assumptions on the optimal solution explained at the beginning of Section
2 imply that we can also restrict ourselves to instances with
$\sum_{i=1}^{m}s_{i}=n$ and furthermore the values of speeds $s_{i}$ are
integral, as in the optimal solution the machine loads are necessarily
integral. (Recall that this is due to the fact that we can modify the speeds
independently of the first-stage algorithm.)

The key ingredient of the improved algorithm is to observe that the
integrality of speeds allows us to use the pigeonhole principle to create
larger bags. Furthermore, with appropriate accounting we can use the
pigeonhole principle iteratively.

Let us demonstrate this on an example. Let $n=13$, $m=10$ and $\rho=1.6$. The
total speed of $10$ machines is $13$, so one machine has speed at least $2$.
This means that one of the machines will have capacity $2\rho=3.2$ and we can
create and assign a bag of size $\lfloor 2\rho\rfloor=3$. Without integrality
of the speeds, only a machine with speed $1.3$ would be guaranteed, so the
capacity would be just above $2$.

To continue iteratively, we cannot reason about the capacity as in Algorithm
GreedyAssignment. Instead, for each bag we reserve some integral amount of
speed on one of the machines. For this accounting, we represent the remaining
unreserved total speed by coins.

In the example above, we pay $2$ coins for a bag of size $3$. This seems like
an overpayment compared to Algorithm GreedyAssignment, as the $2$ coins
correspond to capacity $3.2$, so we waste a capacity of $0.2$. However, after
this step, we are left with $11$ coins among the $10$ machines, and using the
integrality and the pigeonhole principle once more, we are guaranteed to have
one machine with $2$ coins (these coins may be on a different machine or they
may be the ones remaining on the same machine). Thus we can create another bag
of size $3$. Now there are only $9$ coins remaining and we can only create a
bag of size 1 at cost 1. See Figure 5.1 for an illustration. Overall, the
effect of integrality is more significant than the overpayment due to
rounding, and thus we are able to obtain an improved algorithm.

Figure 5.1: Graphical representation of the first three chosen bags for
$n=13$, $m=10$. The dots represent coins and the boxes represent chosen bags.
The number of coins inside a box represent the cost of the bag. Vertical lines
emphasize the multiples of $m$, which determine the bag costs.

Formally, we start Algorithm Bricks with $c=n$ coins. In each round we pay
$z=\lceil c/m\rceil$, create a bag of size $\lfloor z\cdot\rho\rfloor$ and
continue with remaining coins on $m$ machines. The cost of a bag is the number
of coins we pay for it, i.e., $z$ in the algorithm.

Algorithm Bricks

Input: number of bricks $n$; number of machines $m$; number of bags $b$;
desired robustness factor $\rho$

$c\leftarrow n$ $\triangleright$ The initial number of coins is n

for $j\leftarrow 1$ to $b$ do

$z\leftarrow\lceil c/m\rceil$ $\triangleright$ max guaranteed coins on a
machine

$a_{j}\leftarrow\lfloor z\cdot\rho\rfloor$ $\triangleright$ max integer such
that $\operatorname{cost}(a_{j})=z$

$c\leftarrow c-z$

return $a_{1},a_{2},\ldots,a_{b}$

If Algorithm Bricks produces bags of total size at least $n$, we say it is
successful. If the total sum of bag sizes exceeds $n$, we decrease the sizes
of some bags to make the sum equal to $n$. E.g., we can remove some of the
last small bags and then decrease size of the last non-empty bag as needed.

In Section 5.3 we show that this algorithm is sound, namely, we give a
modification of the second stage algorithm algorithm GreedyAssignment for
which we show that a machine with unused speed $z$ always exists and thus we
can assign all bags.

For a general instance, there is always a machine of speed at least $\lceil
n/m\rceil=\lceil\lambda\rceil$, and thus the cost of the first bag is chosen
as $\lceil\lambda\rceil$. The cost will then decrease by 1 every time the
number of coins decreases below a multiple of $m$. Figure 5.2 illustrates
this.

Figure 5.2: Graphical representation of the first chosen bag of size
$\lceil\lambda\rceil$.

Note that the costs of the bags chosen by Bricks do not depend on $\rho$. The
sizes of the bags, however, do depend on $\rho$. See Figure 5.3 below for an
example execution of Bricks for $n=45$ and $m=9$. This execution shows that
Bricks fails for $\rho<1.6$ but succeeds for $\rho=1.6$.

remaining coins $c$ |  $a_{j}$ for $\rho=1.6$ |  $a_{j}$ for $\rho<1.6$
---|---|---
45 | 8 | $<8$
40 | 8 | $<8$
35 | 6 | $\leq 6$
31 | 6 | $\leq 6$
27 | 4 | $\leq 4$
24 | 4 | $\leq 4$
21 | 4 | $\leq 4$
18 | 3 | $\leq 3$
16 | 3 | $\leq 3$
| 46 | $\leq 44$

Figure 5.3:  Tabular and graphical representation of the execution of Bricks
for $n=45$, $m=9$ and $\rho=1.6$. The numbers above bags represent their
sizes. The sum of bag sizes is actually $46>n=45$, to solve this, we can for
example replace one bag of size 3 with a bag of size 2.

###  5.2 Fractional solutions

In general, the cost of the first bag chosen will be $\lceil\lambda\rceil$.
The cost will then decrease by $1$ every time the number of coins decreases
below a multiple of $m$. Roughly speaking, we use approximately $m$ coins for
bags of each size.

We need to show that the created $b$ bags have total size at least $n$. If we
would use exactly $m/z$ bags for each cost $z$, the total size of bags is easy
to compute. However, the integral number of bags of each cost causes rounding
issues when the bag cost decreases and these complicate the calculations.

To structure our analysis, we first modify the solution obtained by Bricks
into a solution that uses possibly non-integral number of bags of each size.
In such a solution, we can use fractions of bags (such as $\frac{4}{5}$ of a
bag of size 8 as in the Figure 5.4). We arrange the modification so that the
total size of bags of cost $z$ is exactly $m$, except for the smallest and
largest bag costs. In the main part of our proof, we bound the rounding error,
i.e., the difference between the sizes of the integral and fractional
solution. To complete the proof, we calculate the total size of bags in the
modified fractional solution, which is easy, and show that it is well above
$n$.

Figure 5.4:  Fractional solution for $n=45$, $m=9$ and $\rho=1.6$ produced by
BricksFract. Notice that we always use only one bag size (cost) between
consecutive multiples of $m$. Compare this to Figure 5.3 where bag cost $5$
“overflows” the line at $4m$ coins.

For the fractional solutions, it is better to use an alternative
representation of the bags by a function $F$ that for each $z$ gives the
number $F(z)$ of bags of cost $z$. The size of $F$ is then defined as the
total size of bags. Recall that a bag of cost $z$ has size $\lfloor
z\cdot\rho\rfloor$. Formally:

######  Definition 5.2.

A fractional solution is a mapping $F:\mathbb{N}\to\mathbb{R}_{0}^{+}$
satisfying $\sum_{z=1}^{\infty}F(z)=b$. The size of fractional solution $F$
for robustness factor $\rho$ is defined as

$\operatorname{size}(F,\rho)=\sum_{z=1}^{\infty}F(z)\cdot\lfloor
z\cdot\rho\rfloor\,.$

We will sometimes use only $\operatorname{size}(F)$ if $\rho$ is clear from
the context.

We start by reformulating Bricks so that it produces the solution directly in
the alternative representation, see Algorithm BricksAlt below. It is easy to
see that Bricks and BricksAlt are equivalent.

Algorithm BricksAlt

Input: number of bricks $n$; number of machines $m$; number of bags $b$

Output: Fractional solution $I$

$r\leftarrow b$ $\triangleright$ $r$ is the remaining number of bags
(integral)

$c\leftarrow n$ $\triangleright$ $c$ is the remaining number of coins
(integral)

$I[z]\leftarrow 0$ for $z\in\mathbb{N}$

while $r>0$ and $c>0$ do

$z\leftarrow\lceil\frac{c}{m}\rceil$ $\triangleright$ $z$ is the bag cost

$x\leftarrow\min\left(r,\lceil\frac{c-m(z-1)}{z}\rceil\right)$
$\triangleright$ $x$ is the (integral) number of bags of cost $z$

$r\leftarrow r-x$

$c\leftarrow c-x\cdot z$

$I[z]\leftarrow x$

return $I$

Bricks and BricksAlt use each bag cost the same number of times.

######  Proof 5.3.

One step of BricksAlt corresponds to several steps of Bricks. Bricks chooses
the bags one by one, and it may choose the same bag cost in several
consecutive iterations. BricksAlt in each step calculates how many bags of
given cost would Bricks use. The key observation is that the expression
$\lceil(c-m(z-1))/z\rceil$ calculates how many bags of cost $z$ are needed to
have at most $m(z-1)$ coins remaining. In other words, it calculates how many
bags of cost $z$ Bricks uses before it starts using bags of cost $z-1$ (or
runs out of bags). Hence both Bricks and BricksAlt use the same number of bags
of cost $z$ for each $z$.

Algorithm BricksFract (see below) is obtained from BricksAlt by removing the
rounding in the calculation of the number of bags $x$.

Algorithm BricksFract

Input: number of bricks $n$; number of machines $m$; number of bags $b$

Output: Fractional solution $F$

$r\leftarrow b$ $\triangleright$ $r$ is the remaining number of bags
(fractional)

$c\leftarrow n$ $\triangleright$ $c$ is the remaining number of coins
(fractional)

$F[z]\leftarrow 0$ for $z\in\mathbb{N}$

while $r>0$ and $c>0$ do

$z\leftarrow\lceil\frac{c}{m}\rceil$

$x\leftarrow\min\left(r,\frac{c-m(z-1)}{z}\right)$ $\triangleright$ $x$ is the
fractional amount of bags of cost $z$

$r\leftarrow r-x$

$c\leftarrow c-x\cdot z$

$F[z]\leftarrow x$

return $F$

The following observation says that the algorithm follows our initial
intuition, namely that for bags of each cost we use exactly $m$ coins, except
for the first and last bag cost used.

######  Definition 5.4.

Let $F$ be a fractional solution, then let $z_{\min}$ and $z_{\max}$ denote
the smallest and largest integers such that $F(z_{\min})>0$ and
$F(z_{\max})>0$.

Let $F$ be a result BricksFract with input $n$ and $m$. Then $F(z)=m/z$ for
every $z$ such that $z_{\min}<z<z_{\max}$.

######  Proof 5.5.

Observe that in every step of the algorithm, except the last one, it holds
that $x=(c-m(z-1))/z$ and thus $c-x\cdot z=m(z-1)$. It follows that in all the
steps except for the first and last ones $x=(mz-m(z-1))/z=m/z$.

Next we observe that the result of BricksFract scales, i.e., essentially it
depends only on $\lambda$. Note also that BricksFract is well defined even for
non-integral $m$ and $n$. Let $\alpha\in\mathbb{R}^{+}$. Suppose BricksFract
produces solution F with $n$ and $m$ as an input and solution $\bar{F}$ with
inputs $\alpha n$ and $\alpha m$. Then $\bar{F}(z)=\alpha F(z)$ for all $z$.
It follows that
$\operatorname{size}(\bar{F},\rho)=\alpha\cdot\operatorname{size}(F,\rho)$.

######  Proof 5.6.

We go through the execution of BricksFract step by step. Suppose that we
multiply both $m$ and $n$ by $\alpha$. Then in every iteration of the loop $r$
is multiplied by $\alpha$, $c$ is multiplied by $\alpha$, $z$ stays the same,
and $x$ is multiplied by $\alpha$.

Now we are ready to bound the difference between the solutions produced by
BricksFract and BricksAlt, i.e., the rounding error.

######  Lemma 5.7.

Let $F$ be the fractional solution produced by BricksFract and $I$ the
solution produced by BricksAlt on the same input. Then

  * •

for $\lambda\leq 5$ it holds that
$\operatorname{size}(I,1.6)\geq\operatorname{size}(F,1.6)$ and

  * •

for $\lambda\leq 60$ it holds that
$\operatorname{size}(I,1.6)\geq\operatorname{size}(F,1.6)-12$.

######  Proof 5.8.

We give an algorithm which transforms $F$ into a solution $F^{\prime}$ that is
almost integral and very close to $I$. Set $\bar{z}$ to be $z_{\min}$ of the
solution $F$ and note that $z_{\max}=\lceil\lambda\rceil$.

We go through the bag costs, denoted by $z$, from $\lceil\lambda\rceil$ down
to $\bar{z}+1$. For each $z$, if $F$ uses non-integral amount of bags of cost
$z$, round it up. This makes the number of bags of cost $z$ equal to their
number in the solution $I$. Then decrease the number of bags of cost $z-1$ so
that the total cost of all bags remains the same. Finally, increase the number
of bags of cost 1 so that the total number of bags stays equal to $b$. See
Figure 5.5 for an illustration.

Figure 5.5: Graphical representation of $F$, $F^{\prime}$ and $I$. In the
first step of the transformation from $F$ to $F^{\prime}$, $\frac{9}{5}$ is
rounded up to 2 and the number of bags of cost 5 (and size 8) increases by
$\frac{1}{5}$. In order to keep the total cost the same, number of bags of
cost 4 (and size 6) is decreased by $\frac{1}{4}$. As a result, total number
of bags decreased by $\frac{1}{4}-\frac{1}{5}=\frac{1}{20}$, hence we add
$\frac{1}{20}$ of a bag of cost 1 (and size 1). This is actually the only step
in which something happens since number of used bags of cost $4$ and $3$ is
already integral. We do not process the bags of cost 2, as $\bar{z}=2$.
Solution $F^{\prime}$ is almost identical to the solution $I$, but has
$\frac{1}{20}$ of bag of cost $1$ instead of $\frac{1}{20}$ of bag of cost 2.

For $z=\bar{z}+1$, the previous procedure could lead to a negative value of
$F^{\prime}(\bar{z})$. In this special case we proceed slightly differently
and instead of rounding $G(z)$ up we only increase it so that
$F^{\prime}(\bar{z})=0$.

We now describe one step of the process formally and analyze it. Let $G$
denote the current fractional solution and let $H$ denote the result of one
transformation step. Let $z$ be the current cost of bags.

We set $H(z)=\lceil G(z)\rceil$, note that $H(z)-G(z)<1$. We want the sum of
costs of bags of costs $z-1$ and $z$ to remain the same, hence we want

$H(z)\cdot z+H(z-1)\cdot(z-1)=G(z)\cdot z+G(z-1)\cdot(z-1)$ (5.1)

to hold. Rearranging (5.1) to an equivalent equation leads to (5.2), so we set

$H(z-1)=G(z-1)+(G(z)-H(z))\cdot\frac{z}{z-1}\,.$ (5.2)

We claim that $H(z-1)>0$ for $z-1>\bar{z}$. Indeed, as $m>144$ and
$z\leq\lceil\lambda\rceil\leq 60$ in the considered case, we have
$G(z-1)=F(z-1)=m/(z-1)>2$ (using also $\bar{z}=z_{\min}<z-1<z_{\max}$). As
$H(z)-G(z)<1$, we get $H(z-1)>G(z-1)-1>0$.

Now we describe the modification in the special case when $H(z-1)$ would
become negative. We have shown above that this can happen only for
$z=\bar{z}+1$, i.e., in the last step. Then we set $H(z-1)=0$ and set

$H(z)=G(z)+(G(z-1)-H(z-1))\frac{z-1}{z}.$

This equation is equivalent to (5.1), which is in turn equivalent to (5.2),
which thus also holds. Furthermore, the fact that the previous procedure would
lead to negative $H(z-1)$ implies that now we have $G(z)\leq H(z)\leq\lceil
G(z)\rceil$ and thus $H(z)-G(z)<1$ holds again.

In both cases, the total number of bags has decreased by

$(G(z)-H(z))+(G(z-1)-H(z-1))=\frac{1}{z-1}(H(z)-G(z))\,.$

Thus we set

$H(1)=G(1)+\frac{1}{z-1}(H(z)-G(z))\,.$

Note that in the transformation step, both the total number of bags and their
total cost remain constant.

Recall that the size of a bag of cost $z$ is $\lfloor z\rho\rfloor$. It
follows that

$\displaystyle\operatorname{size}$ $\displaystyle(H)-\operatorname{size}(G)$
$\displaystyle=(H(z)-G(z))\cdot\lfloor
z\rho\rfloor+(H(z-1)-G(z-1))\cdot\lfloor(z-1)\rho\rfloor+(H(1)-G(1))\cdot\lfloor\rho\rfloor$
$\displaystyle=(H(z)-G(z))\cdot\left(\lfloor
z\rho\rfloor-\frac{z}{z-1}\lfloor(z-1)\rho\rfloor+\frac{1}{z-1}\lfloor\rho\rfloor\right)$

Note that the second factor in the expression above does not depend on the
solution. We call it the transformation factor and for $z$ we denote it by

$f(z)=\left(\lfloor
z\rho\rfloor-\frac{z}{z-1}\lfloor(z-1)\rho\rfloor+\frac{1}{z-1}\lfloor\rho\rfloor\right)\,.$

If $f(z)\geq 0$, the size of the solution could have only increased, as
$H(z)\geq G(z)$, i.e., we have
$\operatorname{size}(H)\geq\operatorname{size}(G)$. If $f(z)<0$, the size of
the solution might have decreased—those are the important (“bad”) cases we
need to bound. We have $H(z)-G(z)<1$, hence
$\operatorname{size}(H)\geq\operatorname{size}(G)+f(z)$ in case of negative
$f(z)$.

Now we sum these bounds over all steps for $z$ from $\lceil\lambda\rceil$ to
$2$ and get

$\operatorname{size}(F^{\prime})-\operatorname{size}(F)\geq\sum_{z=2}^{\lceil\lambda\rceil}\min(0,f(z))$

We give a list of values of $f(z)$ for $z$ from 2 to $60$ and $\rho=1.6$ in
Appendix A.1. For $z\leq 5$ the values $f(z)$ are non-negative, thus for
$\lambda\leq 5$ we get
$\operatorname{size}(F^{\prime})-\operatorname{size}(F)\geq 0$. It can be
verified that the sum of all negative values of $f(z)$ for $z\leq 60$ is
larger than $-12$ and thus for $\lambda\leq 60$ we get
$\operatorname{size}(F^{\prime})-\operatorname{size}(F)>-12$.

Examining the algorithms BricksAlt and BricksFract that generate the solutions
$I$ and $F$, respectively, and the transformation process above shows that the
solution $F$ is step by step transformed towards $I$. In particular,
$I(z)=F^{\prime}(z)$ for all values $z\geq\bar{z}$ (if the special case does
not apply) or ($z\geq\bar{z}+1$ if the special case applies). For the small
values of $z$, the only possible difference is that solution $F^{\prime}$
might have some amount of bags of size 1 instead of some larger bags in
solution $I$. (Note that the total number of bags does not change during the
transformation.) This implies
$\operatorname{size}(I)\geq\operatorname{size}(F^{\prime})$ and the lemma
follows.

To complete the proof we need to show that $\operatorname{size}(F)$ is
sufficiently large so that $\operatorname{size}(I)\geq n$. Actually, as the
previous transformation possibly gives $I$ with a slightly smaller size than
$F$, we need to compensate for this difference which is at most $12$.
Precisely, we need to prove that $\operatorname{size}(F,1.6)\geq n$ for
$\lambda\leq 5$ and $\operatorname{size}(F,1.6)\geq n+12$ for $5<\lambda\leq
60$ and $m\geq 144$.

Since the fractional solution $F$ scales when $m$ and $n$ are scaled, see
Observation 5.5, it is convenient to normalize by $m$ and consider
$(\operatorname{size}(F,1.6)-n)/m$ in the following lemma. Let us call this
crucial quantity normalized brick surplus, as it measures how many bricks we
are able to put in the bags in the fractional solution in addition to $n$
bricks, normalized by $m$.

######  Lemma 5.9.

Let $F$ be a fractional solution produced by BricksFract. Then

  * •

For $\lambda\leq 4$ it holds that $\operatorname{size}(F,1.6)\geq n$.

  * •

For $4\leq\lambda\leq 60$ it holds that $\operatorname{size}(F,1.6)\geq
n+\frac{1}{12}m$.

######  Proof 5.10.

By Observation 5.5, the normalized brick surplus
$\operatorname{size}(F,1.6)-n)/m$ is uniquely determined by $\lambda$, i.e.,
multiplying both $n$ and $m$ by the same constant does not change it.

This means that the normalized brick surplus is a function of $\lambda$.
Furthermore, we claim that the function is piece-wise linear. Suppose we
slowly increase $\lambda$, for example fix $m$ and increase $n$ by $\delta$.
Then $F(z)$ remains constant for all $z$ except $z_{\min}$ and $z_{\max}$ by
Observation 5.2. The number of the largest bags $F(z_{\max})$ increases by
$\delta/\lceil\lambda\rceil$ and $F(z_{\min})$ decreases by the same amount;
this amount is proportional to $\delta$. The function $\operatorname{size}(F)$
is linear in the values of $F(z)$. So the normalized brick surplus is piece-
wise linear with possible breakpoints between the segments at the values of
$\lambda$ when one of the values of $z_{\min}$ or $z_{\max}$ changes.

The value of $z_{\max}$ changes exactly when $\lambda$ is an integer. The
breakpoints where $z_{\min}$ increases can be calculated in the following way:
Execute BricksFract for all integer values of $\lambda\leq 60$. Let us denote
one of such solutions $F$. Take a look at $F(z_{\min})$, if we now slowly
increase $\lambda$, $F(z_{\min})$ will decrease linearly as described above.
Calculate at which point it reaches 0; if it happens before $\lambda$
increases above another integer, we found a point where $z_{\min}$ changes.
The first case of changing $z_{\min}$ is at $\lambda=\frac{11}{3}$ when we
stop using bags of cost 1, see Figure 5.6.

Figure 5.6:  Example of solution produced by BricksFract for $n=11$, $m=3$ and
$\rho=1.6$. Size of this solution is $11.5$ and normalized brick surplus is
$\frac{1}{6}$. The solution does not use any bags of cost 1. However, if
$\lambda$ were smaller, the solution would use bags of size $1$.

The computer-generated tables of values of the normalized brick surplus
function are given in Appendix A.2. The plot of the values is given in Figures
5.7 and 5.8 below.

$0$$2$$4$$6$$8$$10$$0$$0.1$$0.2$$0.3$$\lambda=\frac{n}{m}$normalized brick
surplusNormalized brick surplus as a function of $\lambda$ Figure 5.7: Plot of
normalized brick surplus for small $\lambda$.
$0$$10$$20$$30$$40$$50$$60$$0$$0.2$$0.4$$0.6$$0.8$$\lambda=\frac{n}{m}$normalized
brick surplusNormalized brick surplus as a function of $\lambda$ Figure 5.8:
Plot of normalized brick surplus for large $\lambda$.

The lemma now follows, since the normalized brick surplus is always non-
negative and it is at least $1/12$ for $\lambda\geq 5$. (Note that it is a
constant function equal to $1/12$ for $\lambda\in[4,6]$.)

######  Theorem 5.11.

For $\rho=1.6$ and $\lambda\leq 60$, Algorithm Bricks always succeeds, i.e.,
outputs bags of total size at least $n$.

######  Proof 5.12.

For $\lambda\leq 5$, the first claims in Lemmata 5.9 and 5.7 together prove
$\operatorname{size}(I,1.6)\geq\operatorname{size}(F,1.6)\geq n$.

For $5\leq\lambda\leq 60$ and $m\geq 144$ the second claims in Lemmata 5.9 and
5.7 together prove
$\operatorname{size}(I,1.6)\geq\operatorname{size}(F,1.6)-12\geq n+m/12-12\geq
n+144/12-12=n$.

For $\lambda\leq 60$ and $m\leq 144$ there are only a finitely many instances
and we verify $\operatorname{size}(I,1.6)\geq n$ for them by computer, see
Appendix A.3

We note that our choice of the bounds in the previous two lemmata is somewhat
arbitrary. The plots of the normalized brick surplus suggest that we could
bound it by an appropriate linear function instead of a constant. Also, the
bound on $\operatorname{size}(F)-\operatorname{size}(I)$ can be made smaller
for intermediate values of $\lambda$. These changes would decrease the number
of cases we need to check by a computer program, but would not improve the
robustness factor.

###  5.3 Second stage

We need to show that if Bricks succeeds, in the second stage we can indeed
achieve makespan $\rho$. To do this, we cannot use Algorithm GreedyAssignment
and Theorem 2.1. Instead we modify it to Algorithm IntegralAssignment below,
which copies the coins accounting scheme from Bricks and thus follows the
intuition behind it.

Algorithm IntegralAssignment

Input: bag sizes $a_{1}\geq\cdots\geq a_{b}$; machine speeds
$s_{1}\geq\cdots\geq s_{m}$; desired robustness factor $\rho$

for $i\leftarrow 1$ to $m$ do

$c_{i}\leftarrow s_{i}$ $\triangleright$ Machine $i$ gets $s_{i}$ coins at the
beginning.

$M_{i}=\emptyset$ $\triangleright$ Initialize the assignment

for $k\leftarrow 1$ to $b$ do

$i\leftarrow$ index of the machine with the largest $c_{i}$

$M_{i}\leftarrow M_{i}\cup\\{k\\}$ $\triangleright$ Assign bag $k$ to machine
$i$

$c_{i}\leftarrow c_{i}-\lceil a_{k}/\rho\rceil$ $\triangleright$ Machine $i$
pays for the bag $k$

return $M_{1},\ldots,M_{m}$

######  Theorem 5.13.

Suppose the first-stage algorithm Bricks succeeds, i.e., outputs bags of total
size of at least $n$. Then IntegralAssignment in the second stage produces an
assignment with makespan at most $\rho$.

######  Proof 5.14.

Imagine that Bricks and IntegralAssignment are running in parallel. Bricks
chooses the size of one bag and IntegralAssignment assigns it to a machine.
Note that the values of $c_{i}$ remain integral during the entire execution.

We claim that during the execution the value $c$ in Bricks is at most
$\sum_{i=1}^{m}c_{i}$ for $c_{i}$’s in IntegralAssignment. At the beginning,
the quantities are equal. Suppose that Bricks creates a bag of cost $z$ and
thus decreases $c$ by $z$. Then the bag has size $a=\lfloor
z\cdot\rho\rfloor\leq z\rho$. Thus IntegralAssignment decreases $c_{i}$ by
$\lceil a/\rho\rceil\leq\lceil z\rho/\rho\rceil=z$. Thus the sum of $c_{i}$’s
decreases by at most $z$ and the claim follows.

The claim implies that in each step before creating/assigning a bag of cost
$z$, there exists a machine with $c_{i}\geq z$ in IntegralAssignment. Indeed,
Bricks chooses $z=\lceil c/m\rceil$, thus $m(z-1)<c\leq\sum_{i=1}^{m}c_{i}$
using the previous claim. Hence there exists a machine with $c_{i}>z-1$ and
together with integrality of $c_{i}$ we get $c_{i}\geq z$.

It follows that $c_{i}$’s remain non-negative during the execution. Thus
IntegralAssignment assigned to machine $i$ bags of the total size at most
$s_{i}\cdot\rho$. It follows that the makespan is at most $\rho$.

Theorems 5.1, 5.11, and 5.13 immediately imply our main result.

######  Theorem 5.15.

There exists 1.6-robust algorithm for the case of bricks and $b=m$. ∎

## Conclusions

Our main result still leaves a small gap in the bounds for bricks (equal-
length jobs) and $b=m$ between the lower bound of $e/(e-1)\approx 1.58$ and
our upper bound of $1.6$. Our algorithm Bricks does not admit a smaller
robustness factor than $1.6$, as is shown for $n=45$ and $m=9$ in Figure 5.3.
So a smaller upper bound would need some additional techniques or special
handling of some cases. Eberle et al. [4] give an example that shows a lower
bound for bricks that is larger than $\overline{\rho}(m,m)$ for $m=6$.
Although the value of the bound is below the limit value $e/(e-1)$, this may
be taken as a weak evidence that matching the lower bound may be hard.

The main open problem in this model remains to find a $(2-\varepsilon)$-robust
algorithm for the general case and $b=m$.

#### Acknowledgments

We are grateful to Franziska Eberle for insightful discussions and comments,
and to the anonymous referees for detailed and useful reviews.

## References

  * [1] S. Albers.  Algorithms for dynamic speed scaling.  In T. Schwentick and C. Dürr, editors, Proc. of the 28th Int. Symp. on Theoretical Aspects of Computer Science, STACS 2011, volume 9 of LIPIcs, pages 1–11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011.
  * [2] B. Chen, A. van Vliet, and G. J. Woeginger.  An optimal algorithm for preemptive on-line scheduling.  Oper. Res. Lett., 18(3):127–131, 1995.
  * [3] F. Diedrich, K. Jansen, U. M. Schwarz, and D. Trystram.  A survey on approximation algorithms for scheduling with machine unavailability.  In J. Lerner, D. Wagner, and K. A. Zweig, editors, Algorithmics of Large and Complex Networks - Design, Analysis, and Simulation [DFG priority program 1126], volume 5515 of Lecture Notes in Computer Science, pages 50–64. Springer, 2009.
  * [4] F. Eberle, R. Hoeksma, N. Megow, L. Nölke, K. Schewior, and B. Simon.  Speed-robust scheduling: sand, bricks, and rocks.  Math. Program., 197(2):1009–1048, 2023.  A preliminary version appeared at 22nd IPCO, vol 12707 of LNCS, pages 283–296, Springer, 2021.
  * [5] L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, and L. Stougie.  Universal sequencing on an unreliable machine.  SIAM J. Comput., 41(3):565–586, 2012.
  * [6] D. S. Hochbaum and D. B. Shmoys.  A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach.  SIAM J. Comput., 17(3):539–551, 1988.
  * [7] C. Imreh and J. Noga.  Scheduling with machine cost.  In Proc. of the 3rd Int. Workshop on Randomization and Approximation Techniques in Computer Science and 2nd Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX’99, volume 1671 of Lecture Notes in Computer Science, pages 168–176. Springer, 1999.
  * [8] K. Pruhs.  Speed scaling.  In M. Kao, editor, Encyclopedia of Algorithms - 2016 Edition, pages 2045–2047. Springer, 2016.
  * [9] K. Pruhs, J. Sgall, and E. Torng.  Online scheduling.  In J. Y. Leung, editor, Handbook of Scheduling - Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC, 2004.
  * [10] C. Stein and M. Zhong.  Scheduling when you do not know the number of machines.  ACM Trans. Algorithms, 16(1):9:1–9:20, 2020.  A preliminary version appeared at 29th SODA, pages 1261–1273, ACM, 2018.
  * [11] D. P. Williamson and D. B. Shmoys.  The Design of Approximation Algorithms.  Cambridge University Press, 2011.

##  Appendix A Computer-assisted proofs for bricks

###  A.1 Values of the transformation factor

Let us evaluate

$f(z)=\left(\lfloor
z\rho\rfloor-\frac{z}{z-1}\lfloor(z-1)\rho\rfloor+\frac{1}{z-1}\lfloor\rho\rfloor\right)$

for $\rho=1.6$ and $z\in\\{2,3,\dots,60\\}$. See Figure A.1 for both exact and
approximate values of $f(z)$. You might notice that the signs of $f(z)$ are
periodic (with the exception of first few values) with a period of 5. As a
result, approximately $40\%$ of the values of $f(z)$ are negative and the
table shows that they are all above $-0.6$. Examining and summing these $22$
values leads to the bound of $12$ on
$\operatorname{size}(F)-\operatorname{size}(I)$.

$z$ | $f(z)$ | $\approx f(z)$ |  | $z$ | $f(z)$ | $\approx f(z)$ |  | $z$ | $f(z)$ | $\approx f(z)$
---|---|---|---|---|---|---|---|---|---|---
|  |  |  | 21 | $\mathbf{-\frac{11}{20}}$ | –0.55 |  | 41 | $\mathbf{-\frac{23}{40}}$ | –0.57
2 | $2$ | 2.00 |  | 22 | $\frac{10}{21}$ | 0.48 |  | 42 | $\frac{18}{41}$ | 0.44
3 | $0$ | 0.00 |  | 23 | $\mathbf{-\frac{6}{11}}$ | –0.55 |  | 43 | $\mathbf{-\frac{4}{7}}$ | –0.57
4 | $1$ | 1.00 |  | 24 | $\frac{11}{23}$ | 0.48 |  | 44 | $\frac{19}{43}$ | 0.44
5 | $\frac{3}{4}$ | 0.75 |  | 25 | $\frac{11}{24}$ | 0.46 |  | 45 | $\frac{19}{44}$ | 0.43
6 | $\mathbf{-\frac{2}{5}}$ | -0.40 |  | 26 | $\mathbf{-\frac{14}{25}}$ | –0.56 |  | 46 | $\mathbf{-\frac{26}{45}}$ | –0.58
7 | $\frac{2}{3}$ | 0.67 |  | 27 | $\frac{6}{13}$ | 0.46 |  | 47 | $\frac{10}{23}$ | 0.43
8 | $\mathbf{-\frac{3}{7}}$ | -0.43 |  | 28 | $\mathbf{-\frac{5}{9}}$ | –0.56 |  | 48 | $\mathbf{-\frac{27}{47}}$ | –0.57
9 | $\frac{5}{8}$ | 0.62 |  | 29 | $\frac{13}{28}$ | 0.46 |  | 49 | $\frac{7}{16}$ | 0.44
10 | $\frac{5}{9}$ | 0.56 |  | 30 | $\frac{13}{29}$ | 0.45 |  | 50 | $\frac{3}{7}$ | 0.43
11 | $\mathbf{-\frac{1}{2}}$ | -0.50 |  | 31 | $\mathbf{-\frac{17}{30}}$ | –0.57 |  | 51 | $\mathbf{-\frac{29}{50}}$ | –0.58
12 | $\frac{6}{11}$ | 0.55 |  | 32 | $\frac{14}{31}$ | 0.45 |  | 52 | $\frac{22}{51}$ | 0.43
13 | $\mathbf{-\frac{1}{2}}$ | -0.50 |  | 33 | $\mathbf{-\frac{9}{16}}$ | –0.56 |  | 53 | $\mathbf{-\frac{15}{26}}$ | –0.58
14 | $\frac{7}{13}$ | 0.54 |  | 34 | $\frac{5}{11}$ | 0.45 |  | 54 | $\frac{23}{53}$ | 0.43
15 | $\frac{1}{2}$ | 0.50 |  | 35 | $\frac{15}{34}$ | 0.44 |  | 55 | $\frac{23}{54}$ | 0.43
16 | $\mathbf{-\frac{8}{15}}$ | -0.53 |  | 36 | $\mathbf{-\frac{4}{7}}$ | –0.57 |  | 56 | $\mathbf{-\frac{32}{55}}$ | –0.58
17 | $\frac{1}{2}$ | 0.50 |  | 37 | $\frac{4}{9}$ | 0.44 |  | 57 | $\frac{3}{7}$ | 0.43
18 | $\mathbf{-\frac{9}{17}}$ | -0.53 |  | 38 | $\mathbf{-\frac{21}{37}}$ | –0.57 |  | 58 | $\mathbf{-\frac{11}{19}}$ | –0.58
19 | $\frac{1}{2}$ | 0.50 |  | 39 | $\frac{17}{38}$ | 0.45 |  | 59 | $\frac{25}{58}$ | 0.43
20 | $\frac{9}{19}$ | 0.47 |  | 40 | $\frac{17}{39}$ | 0.44 |  | 60 | $\frac{25}{59}$ | 0.42
Figure A.1: Table with exact and approximate (rounded) values of $f(z)$ for
$\rho=1.6$ and $z\in\\{2,3,\dots,60\\}.$

###  A.2 Brick Surplus

See Figure A.2 for values of normalized brick surplus at integer values of
$\lambda$ and Figure A.3 for values at non-integer breakpoint values of
$\lambda$. Note that the normalized brick surplus sometimes decreases.

$\lambda$ | surplus |  | $\lambda$ | surplus |  | $\lambda$ | surplus
---|---|---|---|---|---|---|---
1 | 0.000 |  | 21 | 0.321 |  | 41 | 0.561
2 | 0.000 |  | 22 | 0.366 |  | 42 | 0.576
3 | 0.000 |  | 23 | 0.377 |  | 43 | 0.576
4 | 0.083 |  | 24 | 0.377 |  | 44 | 0.599
5 | 0.083 |  | 25 | 0.417 |  | 45 | 0.615
6 | 0.083 |  | 26 | 0.405 |  | 46 | 0.615
7 | 0.133 |  | 27 | 0.405 |  | 47 | 0.636
8 | 0.133 |  | 28 | 0.405 |  | 48 | 0.638
9 | 0.244 |  | 29 | 0.406 |  | 49 | 0.658
10 | 0.253 |  | 30 | 0.440 |  | 50 | 0.690
11 | 0.253 |  | 31 | 0.457 |  | 51 | 0.690
12 | 0.297 |  | 32 | 0.457 |  | 52 | 0.709
13 | 0.220 |  | 33 | 0.457 |  | 53 | 0.710
14 | 0.220 |  | 34 | 0.472 |  | 54 | 0.710
15 | 0.252 |  | 35 | 0.500 |  | 55 | 0.728
16 | 0.252 |  | 36 | 0.528 |  | 56 | 0.732
17 | 0.310 |  | 37 | 0.539 |  | 57 | 0.749
18 | 0.276 |  | 38 | 0.539 |  | 58 | 0.765
19 | 0.276 |  | 39 | 0.561 |  | 59 | 0.765
20 | 0.321 |  | 40 | 0.561 |  | 60 | 0.782
Figure A.2: Table of approximate values of the normalized brick surplus for integer values of $\lambda$. bag cost | $\lambda$ | surplus |  | bag cost | $\lambda$ | surplus
---|---|---|---|---|---|---
1 | 3.667 | 0.167 |  | 12 | 33.490 | 0.472
2 | 6.350 | 0.133 |  | 13 | 36.206 | 0.539
3 | 9.044 | 0.253 |  | 14 | 38.923 | 0.563
4 | 11.761 | 0.317 |  | 15 | 41.642 | 0.576
5 | 14.477 | 0.252 |  | 16 | 44.360 | 0.615
6 | 17.188 | 0.321 |  | 17 | 47.076 | 0.638
7 | 19.902 | 0.321 |  | 18 | 49.795 | 0.690
8 | 22.622 | 0.393 |  | 19 | 52.514 | 0.719
9 | 25.338 | 0.430 |  | 20 | 55.231 | 0.732
10 | 28.052 | 0.406 |  | 21 | 57.948 | 0.766
11 | 30.772 | 0.465 |  | 22 | 60.668 | 0.793
Figure A.3: Table of approximate values of the normalized brick surplus at the
points when we stop using bags of given cost.

###  A.3 Small cases for bricks

Here we give a computer program that verifies that algorithm Bricks produces
bags of total size at least $n$ for all instances with $m\leq 144$ and
$\frac{n}{m}\leq 60$.

We provide an implementation in Python 3.11. We represent numbers as fractions
to avoid issues with numerical precision. We implement the equivalent
Algorithm BricksAlt, since it is faster than Algorithm Bricks. The code should
take at most a few minutes to run on modern hardware.

from fractions import Fraction from math import ceil, floor def bricks_alt( n:
int, m: int, ) -> dict[int, Fraction]: """ n: number of jobs m: number of
machines returns: Solution in format {bag_cost: number_of_bags} """ c = n r =
m I = {} while r > 0 and c > 0: z = ceil(Fraction(c, m)) x = min(r,
ceil(Fraction(c - m * (z - 1), z))) c -= x * z r -= x I[z] = x return I rho =
Fraction(8, 5) for m in range(1, 145): for n in range(1, 60 * m + 1): I =
bricks_alt(n, m) solution_size = sum( floor(bag_cost * rho) * bag_count for
bag_cost, bag_count in I.items() ) if solution_size < n: raise Exception(
f"Failed for: {n=} {m=} {rho=} \n Solution: {I}" )


t\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ for which one of the
following holds:

  1. 1.

$|V(G^{\prime})|<|V(G)|$

  2. 2.

$V(G^{\prime})=V(G)\wedge|E(G^{\prime})|<|E(G)|$ and $X$ is a linked tidy
modulator for $(G^{\prime},t)$

###### Proof.

By Theorem 5.18 we can in $\textsc{poly}\left(|G|\right)$ time obtain either a
problem instance $(G^{\prime},t)$ with $\textrm{{TW2D}}\left(G\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq t$ and
$|V(G^{\prime})|<|V(G)|$, or a component separator $Y$ for $(G,t,X)$ with
$|Y|\leq\mathcal{Y}\text{-{bound}}\left(t,|X|\right)$, such that
$|\mathcal{C}(G-(X\cup
Y))|\leq\mathcal{C}\text{-{bound}}\left(t,|X|+|Y|\right)$ and each
$C\in\mathcal{C}(G-(X\cup Y))$ has $|N_{G}(C)\cap Y|\leq 4$. In the former
case, correctness trivially follows. Hence we assume the latter.

Let $C\in\mathcal{C}(G-(X\cup Y))$ for which $|V(C)|$ is maximal. We note that
from Definition 5.3 it trivially follows that $\mathcal{C}\text{-{bound}}$ is
a monotonically increasing function. We use this to derive the minimum size of
$V(C)$:

$\displaystyle|V(C)|$
$\displaystyle\geq\left\lceil\frac{|V(G)|-|X|-|Y|}{|\mathcal{C}(G-(X\cup
Y))|}\right\rceil$
$\displaystyle\geq\left\lceil\frac{\mathcal{G}\text{-{bound}}\left(t,|X|,\mathcal{Y}\text{-{bound}}\left(t,|X|\right)\right)-|X|-\mathcal{Y}\text{-{bound}}\left(t,|X|\right)+1}{\mathcal{C}\text{-{bound}}\left(t,|X|+|Y|\right)}\right\rceil$
$\displaystyle\geq\left\lceil\frac{\mathcal{C}\text{-{bound}}\left(t,|X|{{+}}\mathcal{Y}\text{-{bound}}\left(t,|X|\right)\right){{\cdot}}(1988|X|{{+}}1){{\cdot}}\mathcal{P}\text{-{bound}}\left(t,|X|,4,30|X|{{+}}3\right){{+}}1}{\mathcal{C}\text{-{bound}}\left(t,|X|{{+}}\mathcal{Y}\text{-{bound}}\left(t,|X|\right)\right)}\right\rceil$
$\displaystyle=(1988|X|{{+}}1)\cdot\mathcal{P}\text{-{bound}}\left(t,|X|,4,30|X|{{+}}3\right)+\left\lceil\frac{1}{\mathcal{C}\text{-{bound}}\left(t,|X|{{+}}\mathcal{Y}\text{-{bound}}\left(t,|X|\right)\right)}\right\rceil$
$\displaystyle=(1988|X|{{+}}1)\cdot\mathcal{P}\text{-{bound}}\left(t,|X|,4,30|X|{{+}}3\right)+1$

By Lemma 7.1 we can in $\textsc{poly}\left(|G|\right)$ time obtain a block-cut
tree $T$ of $C$.

######  Case 1 :
$|\mathcal{B}(T)|>\mathcal{P}\text{-{bound}}\left(t,|X|,4,30|X|+3\right)$.

We have by Theorem 7.20 that we can in $\textsc{poly}\left(|G|\right)$ time
apply Reduction 7 or 8 on an edge in $E(G)\setminus E(G[X])$, or Reduction 9
or 10. We let $(G^{\prime},t)$ be the obtained problem instance.

######  Case 1.1 : Reduction 7 or 8 was applied.

By Lemmas 6.8 and 6.10 we have $\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$. By definition of
Reductions 7 and 8 we have $V(G^{\prime})=V(G)\wedge|E(G^{\prime})|<|E(G)|$.
The removal of an edge in $E(G)\setminus E(G[X])$ never increases the number
of internally vertex-disjoint paths between any pair $\\{x,y\\}\subseteq X$,
nor remove an edge between any such a pair. Hence $X$ will be a linked set for
$(G^{\prime},t)$. Because $G^{\prime}$ is a subgraph of $G$ it also holds that
$X$ is a tidy modulator for $G^{\prime}$. Hence, in this case returning
$(G^{\prime},t)$ suffices.

######  Case 1.2 : Reduction 9 or 10 was applied.

By Lemmas 7.6 and 7.15 we have $\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$. By Lemma 7.5, the
definition of Reductions 9 and 10, and Definition 7.3 we have
$|V(G^{\prime})|<|V(G)|$. Hence, in this case returning $(G^{\prime},t)$
suffices.

######  Case 2 :
$|\mathcal{B}(T)|\leq\mathcal{P}\text{-{bound}}\left(t,|X|,4,30|X|+3\right)$.

Because each vertex $v\in V(C)$ is in at least one block $B\in\mathcal{B}(T)$
there must exist some $B\in\mathcal{B}(T)$ with
$|V(B)|\geq\lceil|V(C)|/|\mathcal{B}(T)|\geq 1988|X|+2$. Then by Theorem 6.18
we can in $\textsc{poly}\left(|G|\right)$ time apply Reduction 7 or 8 on an
edge in $E(G)\setminus E(G[X])$. Following the same reasoning as in Case 1.1,
returning the obtained problem instance $(G^{\prime},t)$ suffices.

Because these cases cover all cases, correctness trivially follows. ∎

Lemma 8.1, in essence, corresponds to a single iteration of the while-loop on
lines 6 to 16 in Algorithm 2. This while-loop will continue iterating as long
as Lemma 8.1 yields a problem instance with $|V(G^{\prime})|=|V(G)|$. We only
terminate this while-loop once the number of vertices in the graph have
strictly decreased. The following lemma captures this behaviour:

######  Lemma 8.2.

Let $(G,t)$ be a non-trivial problem instance and let $X$ be a linked tidy
modulator for $(G,t)$. If
$|V(G)|>\mathcal{G}\text{-{bound}}\left(t,|X|,\mathcal{Y}\text{-{bound}}\left(t,|X|\right)\right)$
we can in $\textsc{poly}\left(|G|\right)$ time obtain a problem instance
$(G^{\prime},t)$ with $\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ and
$|V(G^{\prime})|<|V(G)|$.

###### Proof.

We prove using induction on $|E(G)|$.

######  Base case : $E(G)=\emptyset$.

We have $\textsc{TW}\left(G\right)=0$, which contradicts $(G,t)$ being a non-
trivial problem instance. Hence, this case vacuously holds.

######  Inductive step : $E(G)\neq\emptyset$.

By Lemma 8.1 we can in $\textsc{poly}\left(|G|\right)$ time obtain a problem
instance $(G^{\prime},t)$ with $\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ for which either
$|V(G^{\prime})|<|V(G)|$ holds or
$V(G^{\prime})=V(G)\wedge|E(G^{\prime})|<|E(G)|$ and $X$ is a linked tidy
modulator for $(G^{\prime},t)$.

######  Case 1 : $|V(G^{\prime})|<|V(G)|$.

Returning $(G^{\prime},t)$ trivially suffices.

######  Case 2 : $V(G^{\prime})|\not<|V(G)|$ and $(G^{\prime},t)$ is a non-
trivial problem instance.

Correctness immediately follows from the induction hypothesis.

######  Case 3 : $V(G^{\prime})|\not<|V(G)|$ and $(G^{\prime},t)$ is a trivial
problem instance.

Lemma 3.8 yields that we can in
$\textsc{poly}\left(|G^{\prime}|\right)\leq\textsc{poly}\left(|G|\right)$ time
obtain a problem instance $(G^{\prime\prime},t)$ with
$\textrm{{TW2D}}\left(G^{\prime\prime}\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq t$ such that
$|V(G^{\prime\prime})|\leq 4$ or $(G^{\prime\prime},t)$ is a non-trivial
problem instance with $|V(G^{\prime\prime})|<|V(G^{\prime})|$. Because $(G,t)$
is non-trivial we have $|V(G)|>4$, which means that in either case
$|V(G^{\prime\prime})|<|V(G)|$ holds. Hence, returning $(G^{\prime\prime},t)$
suffices.

Because these cases cover all cases, correctness trivially follows. ∎

We finally define a function $\text{{bound}}:{\rm
Nature}\times\mathbb{R}\rightarrow{\rm Nature}$ such that for a given
polynomial time $\varepsilon$-approximation algorithm and a problem instance
$(G,t)$ with $|V(G)|>\text{{bound}}\left(t,\varepsilon\right)$ we can apply a
reduction. This procedure corresponds to lines 2 to 17 in Algorithm 2.

######  Definition 8.2.

$\text{{bound}}\left(t,\varepsilon\right)=\max(4,\mathcal{G}\text{-{bound}}\left(t,\varepsilon
t(3t+4),\mathcal{Y}\text{-{bound}}\left(t,\varepsilon t(3t+4)\right)\right))$

######  Lemma 8.3.

Let $(G,t)$ be a problem instance and let $\mathcal{A}$ be a polynomial time
$\varepsilon$-approximation algorithm for the Treewidth-2 Vertex Deletion
problem. If $V(G)>\text{{bound}}\left(t,\varepsilon\right)$, then we can in
$\textsc{poly}\left(|G|\right)$ time obtain a problem instance
$(G^{\prime},t^{\prime})$ with $\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t^{\prime}\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ and
$|V(G^{\prime})|<|V(G)|\wedge t^{\prime}\leq t$.

###### Proof.

In case $(G,t)$ is a trivial problem instance, correctness immediately follows
from Lemma 3.8. Hence, we assume $(G,t)$ is non-trivial.

From Theorem 5.17 it follows that we can in $\textsc{poly}\left(|G|\right)$
time obtain a problem instance $(G^{\prime},t^{\prime})$ with
$\textrm{{TW2D}}\left(G\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq t^{\prime}$ and
$|V(G^{\prime})|<|V(G)|$ and $t^{\prime}\leq t$, or we obtain a problem
instance $(G^{\prime},t)$ and a linked tidy modulator $X$ for $(G^{\prime},t)$
with $\textrm{{TW2D}}\left(G\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq t$ and
$V(G^{\prime})=V(G)$ and $|X|\leq\varepsilon t(3t+4)$. In case the former
holds correctness trivially follows. Hence, we assume the latter.

We note that from Definitions 5.5 and 8.1 it follows that
$\mathcal{G}\text{-{bound}}$ and $\mathcal{Y}\text{-{bound}}$ are
monotonically increasing functions. Hence, we have
$|V(G^{\prime})|=|V(G)|>\text{{bound}}\left(t,\varepsilon\right)\geq\mathcal{G}\text{-{bound}}\left(t,\varepsilon
t(3t+4),\mathcal{Y}\text{-{bound}}\left(t,\varepsilon
t(3t+4)\right)\right)\geq\mathcal{G}\text{-{bound}}\left(t,|X|,\mathcal{Y}\text{-{bound}}\left(t,|X|\right)\right)$.
Hence, from Lemma 8.2 it follows that we can in
$\textsc{poly}\left(|G^{\prime}|\right)=\textsc{poly}\left(|G|\right)$ time
obtain a problem instance $(G^{\prime\prime},t)$ with
$\textrm{{TW2D}}\left(G^{\prime\prime}\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq t$ and
$|V(G^{\prime\prime})|<|V(G^{\prime})|=|V(G)|$. Returning this problem
instance $(G^{\prime},t)$ trivially suffices. ∎

We can use Lemma 8.3 in a straightforward proof by induction to completely
describe the behaviour expressed by Algorithm 2.

######  Theorem 8.4.

Let $(G,t)$ be a problem instance and let $\mathcal{A}$ be a polynomial time
$\varepsilon$-approximation algorithm for the Treewidth-2 Vertex Deletion
problem. We can in $\textsc{poly}\left(|G|\right)$ time obtain a problem
instance $(G^{\prime},t^{\prime})$ with
$\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t^{\prime}\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ and
$|V(G^{\prime})|\leq\text{{bound}}\left(t,\varepsilon\right)$.

###### Proof.

We prove using induction on $|V(G)|$.

######  Base case : $|V(G)|\leq\text{{bound}}\left(t,\varepsilon\right)$.

Trivially holds because returning $(G,t)$ suffices.

######  Inductive step : $|V(G)|>\text{{bound}}\left(t,\varepsilon\right)$.

By Lemma 8.3 we can in $\textsc{poly}\left(|G|\right)$ time obtain a problem
instance $(G^{\prime},t^{\prime})$ with
$\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t^{\prime}\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ and
$|V(G)^{\prime}|<|V(G)|\wedge t^{\prime}\leq t$. From the induction hypothesis
it follows that we can in
$\textsc{poly}\left(|G^{\prime}|\right)\leq\textsc{poly}\left(|G|\right)$ time
obtain a problem instance $(G^{\prime\prime},t^{\prime\prime})$ with
$\textrm{{TW2D}}\left(G^{\prime\prime}\right)\leq
t^{\prime\prime}\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t^{\prime}$ and
$|V(G^{\prime\prime})|\leq\text{{bound}}\left(t^{\prime},\varepsilon\right)$.
From Definition 8.2 it follows that bound is a monotonically increasing
function, which implies
$|V(G^{\prime\prime})|\leq\text{{bound}}\left(t^{\prime},\varepsilon\right)\leq\text{{bound}}\left(t,\varepsilon\right)$.
Hence, returning $(G^{\prime\prime},t^{\prime\prime})$ suffices.

Because these cases cover all cases, correctness trivially follows. ∎

Using the proof given in Appendix 10, we are now able to provide an explicit
kernel bound.

######  Lemma 8.5 (Appendix 10).

$\text{{bound}}\left(t,\varepsilon\right)=O(\varepsilon^{18}t^{41})$.

######  Theorem 8.6.

Let $(G,t)$ be a problem instance. We can in $\textsc{poly}\left(|G|\right)$
time obtain a problem instance $(G^{\prime},t^{\prime})$ with
$\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t^{\prime}\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ and
$|V(G^{\prime})|=O(t^{41})$.

###### Proof.

Directly follows from Theorem 8.4 and Lemmas 5.2 and 8.5. ∎

##  Chapter 9 Conclusion

We have presented a kernelization algorithm that in
$\textsc{poly}\left(|G|\right)$ time transforms a problem instance $(G,t)$
into a problem instance $(G^{\prime},t^{\prime})$ with
$|V(G^{\prime})|=O(t^{41})$ for which $\textrm{{TW2D}}\left(G\right)\leq
t\Longleftrightarrow\textrm{{TW2D}}\left(G^{\prime}\right)\leq t^{\prime}$
holds. Hence, our algorithm proves that the Treewidth-2 Vertex Deletion admits
a kernel of $O(t^{41})$ vertices, which is the first known explicit kernel
size.

Our kernelization algorithm, when combined with a ‘trivial’
$\binom{|V(G)|}{t}\cdot\textsc{poly}\left(|G|\right)$ brute force algorithm
(i.e. check every candidate subset of $V(G)$ of size $t$ using Lemma 2.2),
yields an explicit $O(t^{41t})\cdot\textsc{poly}\left(|G|\right)$ FPT
algorithm for the Treewidth-2 Vertex Deletion problem. Although this algorithm
is not a single-exponential FPT algorithm, like the algorithms by Kim et al.
[34] and by Fomin et al. [27], this algorithm is the first constructive FPT
algorithm that solves the Treewidth-2 Vertex Deletion problem.

##### Kernel Size

One of the remaining questions is whether, or rather how, a tighter kernel
bound can be obtained. As proven by Dell and van Melkebeek [20], there will
not exist a kernel consisting out of $O(t^{2-\varepsilon})$ edges with
$\varepsilon>0$ unless $\text{coNP}\subseteq\text{NP}/\text{poly}$. Our
current kernel of $O(t^{41})$ vertices is far larger than this potential lower
bound. Hence, we would prefer bringing these bounds closer together.

One of the major causes of the large degree of the polynomial bound, that can
potentially be improved upon, is the large number of components
$\mathcal{C}\text{-{bound}}$ needed to guarantee that Lemma 5.11 will find an
application of Reduction 6.

Another effective approach to decrease the degree of the polynomial is to
reduce the size $\mathcal{Y}\text{-{bound}}$ of component separators. The
potentially easiest way to achieve this would be to lower the
$\mathcal{C}\text{-{bound}}$ term. Other approaches will most likely require
either a redefinition of a component separator or a completely new method to
obtaining these component separators.

Other foreseeable improvements will likely follow from the introduction of new
reduction rules that operate on block-cut trees, or more effective methods to
find applications of existing reduction rules. Nevertheless, as follows from
the derivation in Appendix 10, such improvements will have rather limited
potential due to $\mathcal{P}\text{-{bound}}\left(t,|X|,|N_{G}(C)\cap
Y|,30|X|+3\right)$ only having quintic dependency on parameter $t$. A more
effective approach could involve reducing a block-cut graph (forest) over
graph $G-(X\cup Y)$, opposed to individual components in $G-(X\cup Y)$. This
will likely requiring changing the definition of a component separator $Y$,
due to the currently very limited ‘interaction’ between different components
in $G-(X\cup Y)$.

##### Generalisation to other F-Minor Free Families

An important remaining task is to check whether the method of decomposing
graphs outlined in Chapter 5 can be generalised to other instances of the
$\mathcal{F}$-Minor Cover problem as well. We note that our method of
decomposing graphs is similar to the method of decomposing graphs into near-
protrusions introduced by Fomin et al. [27]. Nevertheless, our method is able
to provide the stronger guarantee that components are adjacent to limit-1
cliques in $X$, opposed to the method by Fomin et al., which would for
Treewidth-2 Vertex Deletion only guarantee that each component is adjacent to
a limit-3 subset in $X$ (see Lemma 25 and 26 in [27]).

The property that sets $N_{G}(C)\cap X$ are limit-1 subsets, opposed to
limit-3 subsets, is essential to the safety of the constructive reduction
rules introduced in Chapters 6 and 7. Although constructive reduction rules
that are safe under the guarantee that $N_{G}(C)\cap X$ is a limit-3 subset
exist (e.g., protrusion replacement would be constructive if the set of
representatives is known), finding such constructive reductions will be much
more difficult.

The question is whether both approaches can be brought together into a single
approach that both provides the stronger limit-1 neighbourhood guarantee and
is applicable to any instance of the $\mathcal{F}$-Minor Cover problem where
$\mathcal{F}$ contains a planar graph. The existence of such an approach would
drastically simplify the creation of constructive kernels for this class of
problems. A complementing question would be to verify whether the limit-$m$
bound by Fomin et al. [27] is tight when the component separator $Y$ is of
size polynomial in $t$. This, because such a proof would yield that the
limit-1 neighbourhood guarantee is not achievable by a generalised
kernelization algorithm that operates on all instances of the
$\mathcal{F}$-Minor Cover problem where $\mathcal{F}$ contains a planar graph.

## References

  * [1] Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski.  Complexity of finding embeddings in a k-tree.  SIAM J. Algebr. Discret. Methods, 8(2):277–284, 1987.  doi:10.1137/0608024.
  * [2] Stefan Arnborg and Andrzej Proskurowski.  Linear time algorithms for NP-hard problems restricted to partial k-trees.  Discret. Appl. Math., 23(1):11–24, 1989.  doi:10.1016/0166-218X(89)90031-0.
  * [3] Stefan Arnborg, Andrzej Proskurowski, and Derek G. Corneil.  Forbidden minors characterization of partial 3-trees.  Discret. Math., 80(1):1–19, 1990.  doi:10.1016/0012-365X(90)90292-P.
  * [4] Marshall W. Bern, Eugene L. Lawler, and A. L. Wong.  Linear-time computation of optimal subgraphs of decomposable graphs.  J. Algorithms, 8(2):216–235, 1987.  doi:10.1016/0196-6774(87)90039-3.
  * [5] Morten Biehl, Nils Klarlund, and Theis Rauhe.  Algorithms for guided tree automata.  In Darrell R. Raymond, Derick Wood, and Sheng Yu, editors, Automata Implementation, First International Workshop on Implementing Automata, WIA ’96, London, Ontario, Canada, August 29-31, 1996, Revised Papers, volume 1260 of Lecture Notes in Computer Science, pages 6–25. Springer, 1996.  doi:10.1007/3-540-63174-7\\_2.
  * [6] Daniel Bienstock and Michael A. Langston.  Algorithmic implications of the graph minor theorem.  In Michael O. Ball, Thomas L. Magnanti, Clyde L. Monma, and George L. Nemhauser, editors, Network Models, Handbooks in Operations Research and Management Science, pages 481–502. Elsevier, 1995.  doi:10.1016/S0927-0507(05)80125-2.
  * [7] Hans L. Bodlaender.  Dynamic programming on graphs with bounded treewidth.  In Timo Lepistö and Arto Salomaa, editors, Automata, Languages and Programming, 15th International Colloquium, ICALP88, Tampere, Finland, July 11-15, 1988, Proceedings, volume 317 of Lecture Notes in Computer Science, pages 105–118. Springer, 1988.  doi:10.1007/3-540-19488-6\\_110.
  * [8] Hans L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.  doi:10.1137/S0097539793251219.
  * [9] Hans L. Bodlaender.  Necessary edges in k-chordalisations of graphs.  J. Comb. Optim., 7(3):283–290, 2003.  doi:10.1023/A:1027320705349.
  * [10] Hans L. Bodlaender.  Fixed-parameter tractability of treewidth and pathwidth.  In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages 196–227. Springer, 2012.  doi:10.1007/978-3-642-30891-8\\_12.
  * [11] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin.  On problems without polynomial kernels.  J. Comput. Syst. Sci., 75(8):423–434, 2009.  doi:10.1016/j.jcss.2009.04.001.
  * [12] Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch.  Preprocessing for treewidth: A combinatorial analysis through kernelization.  SIAM J. Discret. Math., 27(4):2108–2142, 2013.  doi:10.1137/120903518.
  * [13] Hans L. Bodlaender, Arie M. C. A. Koster, and Frank van den Eijkhof.  Preprocessing rules for triangulation of probabilistic networks.  Comput. Intell., 21(3):286–305, 2005.  doi:10.1111/j.1467-8640.2005.00274.x.
  * [14] Krishnendu Chatterjee, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.  Optimal tree-decomposition balancing and reachability on low treewidth graphs.  Technical report, Institute of Science and Technology Austria, 2014.  doi:10.15479/AT:IST-2014-314-v1-1.
  * [15] Jianer Chen, Iyad A. Kanj, and Weijia Jia.  Vertex cover: Further observations and further improvements.  J. Algorithms, 41(2):280–301, 2001.  doi:10.1006/jagm.2001.1186.
  * [16] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algorithms, 3rd Edition.  MIT Press, 2009.  URL: http://mitpress.mit.edu/books/introduction-algorithms.
  * [17] Bruno Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.  doi:10.1016/0890-5401(90)90043-H.
  * [18] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [19] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk.  Solving connectivity problems parameterized by treewidth in single exponential time.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150–159. IEEE Computer Society, 2011.  doi:10.1109/FOCS.2011.23.
  * [20] Holger Dell and Dieter van Melkebeek.  Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.  J. ACM, 61(4):23:1–23:27, 2014.  doi:10.1145/2629620.
  * [21] Reinhard Diestel.  Graph Theory, 5th Edition, volume 173 of Graduate Texts in Mathematics.  Springer, 5 edition, 2017.  doi:10.1007/978-3-662-53622-3.
  * [22] Huib Donkers and Bart M. P. Jansen.  A turing kernelization dichotomy for structural parameterizations of F-minor-free deletion.  J. Comput. Syst. Sci., 119:164–182, 2021.  doi:10.1016/j.jcss.2021.02.005.
  * [23] Huib Donkers, Bart M. P. Jansen, and Michal Wlodarczyk.  Preprocessing for outerplanar vertex deletion: An elementary kernel of quartic size.  In Petr A. Golovach and Meirav Zehavi, editors, 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, volume 214 of LIPIcs, pages 14:1–14:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.IPEC.2021.14.
  * [24] Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, and Mathias Weller.  What is known about vertex cover kernelization?  In Hans-Joachim Böckenhauer, Dennis Komm, and Walter Unger, editors, Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, volume 11011 of Lecture Notes in Computer Science, pages 330–356. Springer, 2018.  doi:10.1007/978-3-319-98355-4\\_19.
  * [25] Paola Festa, Panos M. Pardalos, and Mauricio G. C. Resende.  Feedback set problems.  In Christodoulos A. Floudas and Panos M. Pardalos, editors, Encyclopedia of Optimization, Second Edition, pages 1005–1016. Springer, 2009\.  doi:10.1007/978-0-387-74759-0\\_178.
  * [26] Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh.  Hitting forbidden minors: Approximation and kernelization.  SIAM J. Discret. Math., 30(1):383–410, 2016.  doi:10.1137/140997889.
  * [27] Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh.  Planar F-deletion: Approximation, kernelization and optimal FPT algorithms.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470–479. IEEE Computer Society, 2012.  doi:10.1109/FOCS.2012.62.
  * [28] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.  doi:10.1017/9781107415157.
  * [29] Markus Frick and Martin Grohe.  The complexity of first-order and monadic second-order logic revisited.  Ann. Pure Appl. Log., 130(1-3):3–31, 2004.  doi:10.1016/j.apal.2004.01.007.
  * [30] Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk.  Losing treewidth by separating subsets.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1731–1749. SIAM, 2019.  doi:10.1137/1.9781611975482.104.
  * [31] Yoichi Iwata.  Linear-time kernelization for feedback vertex set.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 68:1–68:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICALP.2017.68.
  * [32] Bart M. P. Jansen and Hans L. Bodlaender.  Vertex cover kernelization revisited - Upper and lower bounds for a refined parameter.  Theory Comput. Syst., 53(2):263–299, 2013.  doi:10.1007/s00224-012-9393-4.
  * [33] Bart M. P. Jansen and Jules J. H. M. Wulms.  Lower bounds for protrusion replacement by counting equivalence classes.  Discret. Appl. Math., 278:12–27, 2020.  doi:10.1016/j.dam.2019.02.024.
  * [34] Eun Jung Kim, Christophe Paul, and Geevarghese Philip.  A single-exponential FPT algorithm for the K${}_{\mbox{\footnotesize 4}}$-minor cover problem.  J. Comput. Syst. Sci., 81(1):186–207, 2015.  doi:10.1016/j.jcss.2014.05.001.
  * [35] Nils Klarlund, Anders Møller, and Michael I. Schwartzbach.  MONA implementation secrets.  Int. J. Found. Comput. Sci., 13(4):571–586, 2002.  doi:10.1142/S012905410200128X.
  * [36] Joachim Kneis and Alexander Langer.  A practical approach to Courcelle’s theorem.  Electron. Notes Theor. Comput. Sci., 251:65–81, 2009.  doi:10.1016/j.entcs.2009.08.028.
  * [37] John M. Lewis and Mihalis Yannakakis.  The node-deletion problem for hereditary properties is NP-complete.  J. Comput. Syst. Sci., 20(2):219–230, 1980.  doi:10.1016/0022-0000(80)90060-4.
  * [38] Annegret Liebers.  Planarizing graphs - A survey and annotated bibliography.  J. Graph Algorithms Appl., 5(1):1–74, 2001.  doi:10.7155/jgaa.00032.
  * [39] László Lovász.  Graph minor theory.  Bull. Amer. Math. Soc., 43(1):75–87, 2005.  doi:10.1090/S0273-0979-05-01088-8.
  * [40] Rolf Niedermeier.  Invitation to Fixed-Parameter Algorithms.  Oxford University Press, 2006.  doi:10.1093/ACPROF:OSO/9780198566076.001.0001.
  * [41] Rolf Niedermeier.  Reflections on multivariate algorithmics and problem parameterization.  In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, volume 5 of LIPIcs, pages 17–32. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.  doi:10.4230/LIPIcs.STACS.2010.2495.
  * [42] Siddharthan Ramachandramurthi.  The structure and number of obstructions to treewidth.  SIAM J. Discret. Math., 10(1):146–157, 1997.  doi:10.1137/S0895480195280010.
  * [43] Neil Robertson and Paul D. Seymour.  Graph minors. V. Excluding a planar graph.  J. Comb. Theory, Ser. B, 41(1):92–114, 1986.  doi:10.1016/0095-8956(86)90030-4.
  * [44] Neil Robertson and Paul D. Seymour.  Graph minors .XIII. The disjoint paths problem.  J. Comb. Theory, Ser. B, 63(1):65–110, 1995.  doi:10.1006/jctb.1995.1006.
  * [45] Neil Robertson and Paul D. Seymour.  Graph minors. XX. Wagner’s conjecture.  J. Comb. Theory, Ser. B, 92(2):325–357, 2004.  doi:10.1016/j.jctb.2004.08.001.
  * [46] Daniel P. Sanders.  On linear recognition of tree-width at most four.  SIAM J. Discret. Math., 9(1):101–117, 1996.  doi:10.1137/S0895480193243043.
  * [47] René van Bevern, Hannes Moser, and Rolf Niedermeier.  Approximation and tidying - A problem kernel for s-plex cluster vertex deletion.  Algorithmica, 62(3-4):930–950, 2012.  doi:10.1007/s00453-011-9492-7.
  * [48] Douglas B. West.  Introduction to Graph Theory.  Prentice Hall, 2001.  URL: https://www.pearson.com/us/higher-education/program/West-Introduction-to-Graph-Theory-2nd-Edition/PGM207840.html.

##  Chapter 10 Derivation Kernel Size

In Theorem 8.4 it is stated that given an $\varepsilon$-approximation
algorithm for the Treewidth-2 Vertex Deletion problem and a problem instance
$(G,t)$, that we can obtain a problem instance $(G^{\prime},t^{\prime})$ with
$\textrm{{TW2D}}\left(G^{\prime}\right)\leq
t^{\prime}\Longleftrightarrow\textrm{{TW2D}}\left(G\right)\leq t$ and
$|V(G^{\prime})|\leq\text{{bound}}\left(t,\varepsilon\right)$. Within this
appendix we derive an asymptotic upper bound to the size of the obtained
problem instance.

We note that in case $t=0$ holds we can obtain a problem instance
$(G^{\prime},t^{\prime})$ with $|V(G^{\prime})|\leq
4\leq\text{{bound}}\left(t,\varepsilon\right)$, as follows from Definitions
3.1 and 8.2 and Lemma 3.8. Hence, for this reason it remains to derive an
upper bound to the case where $t>0$.

As discussed in Section 10, we have that $\varepsilon\geq 1$ will hold for any
$\varepsilon$-approximation algorithm for the Treewidth-2 Vertex Deletion
problem.

To derive an upper bound we will make use of the Definitions 5.3, 5.5, 7.2,
7.3, 8.1, and 8.2. We list these definitions below:

$\displaystyle\mathcal{C}\text{-{bound}}\left(t,x\right)$
$\displaystyle=\binom{x}{3}(t+1)+\binom{x}{2}(2t+3)$
$\displaystyle\mathcal{Y}\text{-{bound}}\left(t,x\right)$
$\displaystyle=6\binom{x}{2}(3t+3+\mathcal{C}\text{-{bound}}\left(t,x+3t+3\right))$
$\displaystyle\mathcal{L}\text{-{bound}}\left(t,x,y\right)$
$\displaystyle=y(x+y-1)(t+2)+x+y$
$\displaystyle\mathcal{P}\text{-{bound}}\left(t,x,y,k\right)$
$\displaystyle=\max(1,\mathcal{L}\text{-{bound}}\left(t,x,y\right)(2k+3)+3976kxy-3k-4)$
$\displaystyle\mathcal{G}\text{-{bound}}\left(t,x,y\right)$
$\displaystyle=\mathcal{C}\text{-{bound}}\left(t,x{{+}}y\right)\cdot(1988x+1)\cdot\mathcal{P}\text{-{bound}}\left(t,x,4,30x{{+}}3\right)+x+y$
$\displaystyle\text{{bound}}\left(t,\varepsilon\right)$
$\displaystyle=\max(4,\mathcal{G}\text{-{bound}}\left(t,\varepsilon
t(3t+4),\mathcal{Y}\text{-{bound}}\left(t,\varepsilon t(3t+4)\right)\right))$
We will derive an upper bound to the value of
$\text{{bound}}\left(t,\varepsilon\right)$ using a bottom up approach by first
analysing upper-bounds to the values of sub-formulas. For notation convenience
we will define $x=\varepsilon t(3t+4)$ and we define
$y=\mathcal{Y}\text{-{bound}}\left(t,x\right)$. We first derive an upper bound
to the value of $x$ $\displaystyle x$ $\displaystyle=\varepsilon t(3t+4)$
$\displaystyle\leq\varepsilon t(3t+4t)$ $\displaystyle\leq 7\varepsilon t^{2}$
We next derive an upper bound to the value of
$\mathcal{C}\text{-{bound}}\left(t,x+3t+3\right)$
$\displaystyle\mathcal{C}\text{-{bound}}\left(t,x{{+}}3t{{+}}3\right)$
$\displaystyle=\binom{x+3t+3}{3}(t+1)+\binom{x+3t+3}{2}(2t+3)$
$\displaystyle\leq 2t\binom{7\varepsilon t^{2}+3t+3}{3}+5t\binom{7\varepsilon
t^{2}+3t+3}{2}$ $\displaystyle\leq 2t\binom{13\varepsilon
t^{2}}{3}+5t\binom{13\varepsilon t^{2}}{2}$ $\displaystyle<2t\cdot
2197\varepsilon^{3}t^{6}+5t\cdot 169\varepsilon^{2}t^{4}$ $\displaystyle\leq
5239\varepsilon^{3}t^{7}$ We next derive an upper bound to $y$. $\displaystyle
y$ $\displaystyle=\mathcal{Y}\text{-{bound}}\left(t,x\right)$
$\displaystyle=6\binom{x}{2}(3t+3+\mathcal{C}\text{-{bound}}\left(t,x+3t+3\right))$
$\displaystyle<6\binom{7\varepsilon t^{2}}{2}(3t+3+5239\varepsilon^{3}t^{7})$
$\displaystyle<6\cdot 49\varepsilon^{2}t^{4}\cdot 5245\varepsilon^{3}t^{7}$
$\displaystyle\leq 1542030\varepsilon^{5}t^{11}$ We next derive an upper bound
to $\mathcal{L}\text{-{bound}}\left(t,x,4\right)$.
$\displaystyle\mathcal{L}\text{-{bound}}\left(t,x,4\right)$
$\displaystyle=4(x+4-1)(t+2)+x+4$ $\displaystyle\leq 4\cdot 3t(7\varepsilon
t^{2}+3)+7\varepsilon t^{2}+4$ $\displaystyle<12t\cdot 10\varepsilon
t^{2}+11\varepsilon t^{2}$ $\displaystyle\leq 131\varepsilon t^{3}$ We next
derive an upper bound to $\mathcal{P}\text{-{bound}}\left(t,x,4,30x+3\right)$.
$\displaystyle\mathcal{P}\text{-{bound}}\left(t,x,4,30x{{+}}3\right)$
$\displaystyle=\max(1,\mathcal{L}\text{-{bound}}\left(t,x,4\right)(60x+9)+15904x(30x+3)-90x-11)$
$\displaystyle\leq\max(1,131\varepsilon t^{3}\cdot(420\varepsilon
t^{2}+9)+15904\cdot 7\varepsilon t^{2}(210\varepsilon t^{2}+3))$
$\displaystyle\leq\max(1,131\varepsilon t^{3}\cdot 429\varepsilon
t^{2}+111328\varepsilon t^{2}\cdot 213\varepsilon t^{2})$ $\displaystyle\leq
23769063\varepsilon^{2}t^{5}$ We next derive an upper bound to
$\mathcal{C}\text{-{bound}}\left(t,x+y\right)$.
$\displaystyle\mathcal{C}\text{-{bound}}\left(t,x+y\right)$
$\displaystyle=\binom{x+y}{3}(t+1)+\binom{x+y}{2}(2t+3)$
$\displaystyle<2t\binom{7\varepsilon
t^{2}+1542030\varepsilon^{5}t^{11}}{3}+5t\binom{7\varepsilon
t^{2}+1542030\varepsilon^{5}t^{11}}{2}$ $\displaystyle\leq
2t\binom{1542037\varepsilon^{5}t^{11}}{3}+5t\binom{1542037\varepsilon^{5}t^{11}}{2}$
$\displaystyle<2t\cdot 3666776026137044653\varepsilon^{15}t^{33}+5t\cdot
2377878109369\varepsilon^{10}t^{22}$ $\displaystyle\leq
7333563941664636151\varepsilon^{15}t^{34}$ Using these previous derivations,
we will now derive an upper bound to
$\text{{bound}}\left(t,\varepsilon\right)$. We note that in this derivation we
use the observation that $t>0$ and $\varepsilon\geq 1$ yields $x=\varepsilon
t(3t+4)\geq 7\geq 4$. $\displaystyle\text{{bound}}\left(t,\varepsilon\right)$
$\displaystyle=\max(4,\mathcal{G}\text{-{bound}}\left(t,\varepsilon
t(3t+4),\mathcal{Y}\text{-{bound}}\left(t,\varepsilon t(3t+4)\right)\right))$
$\displaystyle=\max(4,\mathcal{G}\text{-{bound}}\left(t,x,\mathcal{Y}\text{-{bound}}\left(t,x\right)\right))$
$\displaystyle=\max(4,\mathcal{G}\text{-{bound}}\left(t,x,y\right))$
$\displaystyle=\mathcal{C}\text{-{bound}}\left(t,x{{+}}y\right)\cdot(1988x+1)\cdot\mathcal{P}\text{-{bound}}\left(t,x,4,30x{{+}}3\right)+x+y$
$\displaystyle<7333563941664636151\varepsilon^{15}t^{34}{{\cdot}}13917\varepsilon
t^{2}{{\cdot}}23769063\varepsilon^{2}t^{5}{{+}}1542037\varepsilon^{5}t^{11}$
$\displaystyle\leq 2425899315517822591524501413458\varepsilon^{18}t^{41}$ When
$t>0$ we can conclude
$\text{{bound}}\left(t,\varepsilon\right)<2425899315517822591524501413458\varepsilon^{18}t^{41}$.
Hence, we have
$\text{{bound}}\left(t,\varepsilon\right)\leq\max(4,2425899315517822591524501413458\varepsilon^{18}t^{41})=O(\varepsilon^{18}t^{41})$.