# New Support Size Bounds for Integer Programming,
Applied to Makespan Minimization on Uniformly Related Machines

Sebastian Berndt University of Lübeck, Institute for Theoretical Computer
Science, Lübeck, Germany<EMAIL_ADDRESS>Hauke Brinkop Kiel
University, Kiel, Germany<EMAIL_ADDRESS>Partially supported by
the DFG Project  Fein-granulare Komplexität und Algorithmen für Scheduling und
Packungen, JA 612 /25-1 Klaus Jansen Kiel University, Kiel, Germany.
<EMAIL_ADDRESS>Partially supported by the DFG Project Fein-
granulare Komplexität und Algorithmen für Scheduling und Packungen, JA 612
/25-1 Matthias Mnich Hamburg University of Technology, Institute for
Algorithms and Complexity, Hamburg, Germany<EMAIL_ADDRESS>Tobias
Stamm Hamburg University of Technology, Institute for Algorithms and
Complexity, Hamburg, Germany<EMAIL_ADDRESS>
###### Abstract

Mixed-integer linear programming (MILP) is at the core of many advanced
algorithms for solving fundamental problems in combinatorial optimization. The
complexity of solving MILPs directly correlates with their support size, which
is the minimum number of non-zero integer variables in an optimal solution. A
hallmark result by Eisenbrand and Shmonin (_Oper. Res. Lett._ , 2006) shows
that any feasible integer linear program (ILP) has a solution with support
size $s\leq 2m\cdot\log(4m\Delta)$, where $m$ is the number of constraints,
and $\Delta$ is the largest coefficient in any constraint.

Our main combinatorial result are improved support size bounds for ILPs.

To improve granularity, we analyze for the largest $1$-norm $A_{\max}$ of any
column of the constraint matrix, instead of $\Delta$. We show a support size
upper bound of $s\leq m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})$, by
deriving a new bound on the -1 branch of the Lambert $\mathcal{W}$ function.
Additionally, we provide a lower bound of $m\log(A_{\max})$, proving our
result asymptotically optimal. Furthermore, we give support bounds of the form
$s\leq 2m\cdot\log(1.46A_{\max})$. These improve upon the previously best
constants by Aliev. et. al. (_SIAM J. Optim._ 2018), because all our upper
bounds hold equally with $A_{\max}$ replaced by $\sqrt{m}\Delta$.

Our main algorithmic result are the fastest known approximation schemes for
fundamental scheduling problems, which use the improved support bounds as one
ingredient.

First, we design an efficient approximation scheme (EPTAS) for makespan
minimization on uniformly related machines ($Q||C_{\max}$). Our EPTAS yields a
$(1+\varepsilon)$-approximation for $Q||C_{\max}$ on $N$ jobs in time
$2^{\mathcal{O}(1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon)))}+\mathcal{O}(N)$,
which improves over the previously fastest algorithm by Jansen, Klein and
Verschae (_Math. Oper. Res._ , 2020) with run time
$2^{\mathcal{O}(1/\varepsilon\log^{4}(1/\varepsilon))}+N^{\mathcal{O}(1)}$.
Arguably, our approximation scheme is also simpler than all previous EPTASes
for $Q||C_{\max}$, as we reduce the problem to a novel MILP formulation which
greatly benefits from the small support.

Second, we consider $Q|\mathit{HM}|C_{\max}$, which is the problem
$Q||C_{\max}$ with high-multiplicity encoding where _both_ jobs and machines
are given as few distinct types according to their processing times and
speeds. Until now, not even a constant-factor approximation was known for this
problem. We give the first EPTAS for $Q|\mathit{HM}|C_{\max}$, with run time
${2^{\mathcal{O}(1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon)))}+\langle\mathcal{I}\rangle^{\mathcal{O}(1)}}$.

Third, we consider the problem $R_{K}Q||C_{\max}$, where each job can have up
to $K$ distinct processing times, depending on the type of machine they get
processed on, and machine speeds are uniformly related. We give an EPTAS for
$R_{K}Q||C_{\max}$ with run time
${2^{\mathcal{O}(K\log(K)1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon)))}+\mathcal{O}(KN)}$,
thereby reducing the previously best exponent $\tilde{\mathcal{O}}(K\cdot
1/\varepsilon^{3})$ by Jansen and Maack (_Algorithmica_ , 2019) down to
$\tilde{\mathcal{O}}(K\cdot 1/\varepsilon)$.

##  1 Introduction

The Integer Linear Programming (ILP) problem is to find an optimal integral
solution $\bm{x}^{\star}\in\mathbb{Z}^{n}_{\geq 0}$, which minimizes a linear
objective $\bm{c}^{\intercal}\bm{x}$ subject to a system $A\bm{x}=\bm{b}$ of
$m$ linear constraints. In the Mixed-Integer Linear Programming (MILP)
problem, the solution sought is a pair
$(\bm{x}^{\star},\bm{y}^{\star})\in\mathbb{Z}^{n}_{\geq
0}\times\mathbb{Q}^{r}_{\geq 0}$, which minimizes
$\bm{c}^{\intercal}(\bm{x}\leavevmode\nobreak\ \bm{y})$ subject to
$A\bm{x}+B\bm{y}=\bm{b}$. Solving (M)ILPs is at the core of many advanced
algorithms for fundamental combinatorial optimization problems. Very often,
the run time of these algorithms scales with the _support size_ of the
(M)ILPs, which is the smallest number of non-zero entries in an optimal
solution $\bm{x}^{\star}$ resp. $(\bm{x}^{\star},\bm{y}^{\star})$. Thus,
support size bounds have found applications all over computer science, for
example in scheduling [5, 35], logic [40, 46], and even complexity theory
[22]. Therefore, the smaller the support size, the better these results
become. Hence, an important research direction is to prove strong upper bounds
on the support size of (M)ILPs. The original result on support size bounds,
which is already finding its way into the standard curriculum of integer
programming courses [49, Lemma 6.1] is:

######  Proposition 1 (Eisenbrand, Shmonin [15, Thm. 1(ii)]).

Any feasible and bounded ILP with $m$ constraints has a solution with support
size $s\leq 2m\log(4m\Delta)$, where $\Delta$ is the largest absolute value of
any entry in the constraint matrix $A$.

Aliev et al. [2] showed the best general Eisenbrand-Shmonin-style bound
$2m\log(2\sqrt{m}\Delta)$ on the support size for any ILP. For the special
cases of positively space spanning matrices [3], and in the average case over
all right-hand sides [45], results on the order of $\mathcal{O}(m)$ have
recently been obtained. One important application of the Eisenbrand-Shmonin
bound are efficient polynomial-time approximation schemes (EPTAS) for
scheduling problems [29]. An EPTAS computes, for any problem instance
$\mathcal{I}$ and any $\varepsilon>0$, a solution whose value is within
$(1+\varepsilon)$ of the optimal solution value in time
$f(1/\varepsilon)\langle\mathcal{I}\rangle^{\mathcal{O}(1)}$, where
$\langle\mathcal{I}\rangle$ denotes the encoding size of $\mathcal{I}$.
Several EPTAS were devised for the classical scheduling problem of makespan
minimization on uniformly related machines. This problem is denoted as
$Q||C_{\max}$ in Graham’s 3-field notation [19]. The input to $Q||C_{\max}$ is
a set $\mathcal{J}$ of $N$ jobs, each of which is characterized by an integer
processing time $p_{j}$, and a set $\mathcal{M}$ of $M$ machines, each of
which is characterized by an integer speed $s_{i}$. The goal is to find an
assignment (or schedule) $\sigma:\mathcal{J}\rightarrow\mathcal{M}$ of jobs to
machines, which minimizes the maximum completion time
$C_{\max}\coloneqq\max_{i\in\mathcal{M}}\sum_{j\in\sigma^{-1}(i)}p_{j}/s_{i}$
of any machine. Problem $Q||C_{\max}$ is well-known to be $\mathsf{NP}$-hard,
even in the special case of unit speeds $s_{1}=\ldots=s_{m}$, but still
approximable to an arbitrary precision, in contrast to the setting of
unrelated machines. The previously fastest EPTAS for $Q||C_{\max}$ is due to
Jansen, Klein and Verschae [35, 36], and runs in time
$2^{\mathcal{O}\left(1/\varepsilon\log^{4}\left(1/\varepsilon\right)\right)}+N^{\mathcal{O}(1)}$.
Since their result first appeared in 2016, it has been an open question
whether the exponential dependency on $1/\varepsilon$ can be improved. In
particular, there is still a significant gap to the best-known lower bound,
which shows that a run time of
$2^{\mathcal{O}\left((1/\varepsilon)^{1-\delta}\right)}+N^{\mathcal{O}(1)}$ is
not possible for any $\delta>0$, assuming the Exponential-Time Hypothesis
[13]. It is unknown, whether this gap can be improved to $\delta=0$, even
under stronger assumptions such as Gap-ETH [43]. Further, a gap remains to the
best-known run time
$2^{\mathcal{O}\left(1/\varepsilon\log\left(1/\varepsilon\right)\right)\log\left(\log\left(1/\varepsilon\right)\right)}+N^{\mathcal{O}(1)}$
for the case of unit speeds $s_{1}=\ldots=s_{m}$ [8], which correlates with
the interesting question about the gap in complexity between solving ILPs and
MILPs with few constraints.

###  1.1 Our Results

####  1.1.1 Combinatorial results

Our main combinatorial result is an improvement on the fundamental Eisenbrand-
Shmonin bound on the support size of any ILP with regard to a new parameter.
Namely, we replace the dependence on the largest absolute value $\Delta$ of
any entry in the constraint matrix $A$ by the parameter
$A_{\max}\coloneqq\max_{i}\|A_{i}\|_{1}$, the largest $1$-norm of any column
$A_{i}$ in $A$:

######  Theorem 2.

Any feasible bounded ILP with $m$-row constraint matrix $A$ and largest column
$1$-norm $A_{\max}$ has an optimal solution with support size $s\leq
m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})$.

Additionally, we derive support size bounds of the form $s\leq
2m\cdot(1.46A_{\max})$. Because all our upper bounds can equally be derived
with $A_{\max}$ replaced by $\sqrt{m}\Delta$, they also improve on the
constants of Aliev et. al. [2].

For the parameter $A_{\max}$, we can show an asymptotically matching lower
bound on the support size of an optimal solution:

######  Theorem 3.

For any $m\in\mathbb{Z}_{\geq 0}$ and any $A_{\max}\in\mathbb{Z}_{\geq 1}$,
there is an ILP with $m$ constraints, $n\coloneqq
m\cdot(\lfloor\log(A_{\max})\rfloor+1)\geq m\cdot\log(A_{\max})$ variables,
and maximum $1$-norm $A_{\max}$ of column vectors in the constraint matrix,
whose unique optimal solution is the $\bm{1}$-vector.

To obtain this lower bound, we adapting the previously best lower bound of
$m\log(\Delta)$ on the support size of an optimal solution by Berndt, Jansen
and Klein [7].

####  1.1.2 Algorithmic results

We use our upper bounds on the support sizes of optimal solutions to ILPs from
Theorem 2 as _one_ ingredient to obtain new algorithmic results. Namely, we
design a new EPTAS for $Q||C_{\max}$, which is asymptotically faster than all
previous EPTAS for $Q||C_{\max}$; see Table 1 for a survey of prior work on
approximation algorithms for $Q||C_{\max}$.

######  Theorem 4.

There is an algorithm for $Q||C_{\max}$ that, for any $\varepsilon>0$,
computes a $(1+\varepsilon)$-approximate schedule for any set of $N$ jobs in
time
$2^{\mathcal{O}\left(1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon))\right)}+\mathcal{O}(N)$.

Compared to previous works, we devise a novel MILP formulation for
$Q||C_{\max}$ whose constraint matrix has small column norm. Solving this new
formulation not only yields the fastest known EPTAS for $Q||C_{\max}$, but
also an EPTAS which is conceptually much simpler than all previous ones. In
particular, we introduce the following simplifications in our algorithm
compared to the previous EPTAS results:

  * •

In contrast to all other previous algorithms, we do not need a case
distinction that splits the algorithm and its analysis into three or four
different cases, depending on the processing time ratios and numbers of
machines. Our algorithm handles all these cases simultaneously, only incurring
a small increase in the constants hidden in the $\mathcal{O}$ terms.

  * •

We set up an MILP where both jobs and machines with similar size and speed are
combined into few distinct job and machine classes. All but the longest jobs
and machines are then scheduled fractionally. Rounding the fractional
allocations for relatively tiny jobs in a machine class was usually done via a
separate algorithm by Lenstra, Shmoys, and Tardos [42]. Instead, we pack these
jobs with a simple greedy strategy.

  * •

We assign relatively huge jobs of each rounded machine speed using basic
linear program properties. This creates a linear instead of logarithmic
overhead, which we can accommodate by increasing the number of integer
variables by a constant factor. Previous EPTAS mostly used a complex algorithm
by Jansen [30] for a particular bin packing problem.

The only remaining algorithm used as a black-box is the well-known algorithm
by Lenstra [41] for solving MILPs with constant dimension (resp. its
improvement due to Kannan [37]). Due to these simplifications we can easily
extend our approach to further scheduling problems.

authors | year | approximation | run time |
---|---|---|---|---
Gonzales, Ibarra, Sahni [18] | 1977 | $2-\frac{2}{M+1}$ | $\mathcal{O}(N\log(N))$ |
Cho, Sahni [14] | 1980 | $1+\sqrt{\frac{M-1}{2}}$ | $\mathcal{O}(N\log(N))$ |
Woeginger [51] | 1999 | $2-\frac{1}{M}$ | $\mathcal{O}(N\log(N))$ |
Hochbaum, Shmoys [27] | 1988 | $1+\varepsilon$ | $N^{\mathcal{O}(1/\varepsilon^{2}\log(1/\varepsilon))}$ |
Azar, Epstein [4] | 1998 | $1+\varepsilon$ | $N^{\mathcal{O}(1/\varepsilon^{2})}$ |
Jansen [29] | 2010 | $1+\varepsilon$ | $2^{\mathcal{O}(1/\varepsilon^{2}\log^{3}(1/\varepsilon))}$ | ${}+N^{\mathcal{O}(1)}$
Jansen, Robenek [32] | 2012 | $1+\varepsilon$ | $2^{\mathcal{O}(1/\varepsilon\log(1/\varepsilon)\cdot C_{\varepsilon})}$ | ${}+N^{\mathcal{O}(1)},\text{note}$
Jansen, Klein, Verschae [35, 36] | 2016 | $1+\varepsilon$ | $2^{\mathcal{O}\left(1/\varepsilon\log^{4}\left(1/\varepsilon\right)\right)}$ | ${}+N^{\mathcal{O}(1)}$
_This paper_ | 2023 | $1+\varepsilon$ | $2^{\mathcal{O}\left(1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon))\right)}$ | ${}+\mathcal{O}(N)$
Table 1: History of complexity results for approximating $Q||C_{\max}$.

To show the versatility of our approach, we also applied it to three different
applications.

High-Multiplicity Scheduling. We study the problem $Q|\mathit{HM}|C_{\max}$,
where both jobs _and_ machines are given in the succinct high-multiplicity
encoding. That is, we are given a list $p_{1},\ldots,p_{d}$ of job processing
times and for each $p_{j}$ the number $n_{j}$ of jobs with processing time
$p_{j}$; and a list $s_{1},\ldots,s_{\tau}$ of machine speeds and for each
$s_{t}$ the number $m_{t}$ of machines with speed $s_{t}$. All numbers are
encoded in binary, thus the input size can be exponentially smaller than in
the standard encoding, which lists jobs one by one.

We are not aware of any constant-factor approximation for $Q|HM|C_{\max}$,
only for the more restricted setting where only the jobs are given in a high-
multiplicity encoding [16]. We give the first approximation algorithm for this
general high-multiplicity setting.

######  Theorem 5.

There is an algorithm for $Q|\mathit{HM}|C_{\max}$ that, given any instance
$\mathcal{I}$ with preemptively feasible makespan $T$, computes a schedule
with makespan at most $T+p_{\max}$ in time
$\mathcal{O}(\langle\mathcal{I}\rangle)$.

Here, a preemptively feasible makespan is a feasible makespan for the
preemptive relaxation, where we allow interruption and resumption of jobs on
different machines. This directly implies a linear-time $2$-approximation for
$P|\mathit{HM}|C_{\max}$ (where all machines have speed $1$).

Next, we obtain a similar result for the case of uniformly related machines:

######  Corollary 6.

There is an algorithm for $Q|\mathit{HM}|C_{\max}$ that, for any
$\varepsilon>0$, computes a $(2+\varepsilon)$-approximate schedule for any
instance $\mathcal{I}$ in time
$\mathcal{O}(\log(\varepsilon)\cdot\langle\mathcal{I}\rangle)$.

Eventually, we show how to adapt Theorem 4 to the high-multiplicity setting:

######  Corollary 7.

There is an algorithm for $Q|\mathit{HM}|C_{\max}$ that, for any
$\varepsilon>0$, computes a $(1+\varepsilon)$-approximate schedule for any
instance $\mathcal{I}$ in time
$2^{\mathcal{O}(1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon)))}+\langle\mathcal{I}\rangle^{\mathcal{O}(1)}$.

Few Different Machine Speeds. In the special case of $Q||C_{\max}$ with only
$k$ distinct machine speeds, we are able to significantly improve the run time
of our algorithm.

######  Theorem 8.

There is an algorithm for $Q||C_{\max}$ that, for any $\varepsilon>0$,
computes a $(1+\varepsilon)$-approximate schedule for any set of $N$ jobs and
$k$ distinct machine speeds in time $2^{\mathcal{O}\left(k\cdot
1/\varepsilon\log(1/\varepsilon)\log(\log(1/\varepsilon)))\right)}+\mathcal{O}(N)$.

Few Different Uniform Machine Types. Jansen and Maack [31] considered the
generalization of $Q||C_{\max}$ known as $R_{K}Q||C_{\max}$, where each job
can have up to $K$ different processing times. Any machine belongs to one of
$K$ distinct types, which determines the processing times of the jobs.
Machines of the same type can still have different uniform speeds. Jansen and
Maack [31] gave an EPTAS for $R_{K}Q||C_{\max}$ with run time
$2^{\mathcal{O}(K\log(K)1/\varepsilon^{3}\log^{5}(1/\varepsilon))}+\mathcal{O}(K\cdot
N)$. We apply our novel techniques to reduce the exponent from
$\widetilde{\mathcal{O}}(K\cdot 1/\varepsilon^{3})$ down to
$\widetilde{\mathcal{O}}(K\cdot 1/\varepsilon)$:

######  Theorem 9.

There is an algorithm for $R_{K}Q||C_{\max}$ that, for any $\varepsilon>0$,
computes a $(1+\varepsilon)$-approximate schedule for any set of $N$ jobs in
time
$2^{\mathcal{O}(K\log(K)1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon)))}+\mathcal{O}(K\cdot
N)$.

##  2 Preliminaries

We use $\log(2)=1$, i.e., base $2$ logarithms and denote Euler’s number by
$e\coloneqq\exp(1)$. For a vector $\bm{v}$, let
$v_{\min}\coloneqq\min_{\ell}v_{\ell}$ and
$v_{\max}\coloneqq\max_{\ell}v_{\ell}$ be its extremal entries and
$\operatorname{supp}(\bm{v})\coloneqq\\{\ell\mid\bm{v}_{\ell}\neq 0\\}$ its
_support_ , i.e., the set of indices with non-zero entries. For an instance
$\mathcal{I}$, its _encoding size_ $\langle\mathcal{I}\rangle$ is given by
$\langle\mathcal{I}\rangle\coloneqq\sum_{x\in I}(\log(|x|+1)+1)$, the sum over
the sizes in binary representations of all quantities. For example, an
instance $\mathcal{I}$ of $Q||C_{\max}$ has size $\langle\mathcal{I}\rangle$
logarithmic in the job processing times and machine speeds, but linear in the
number of jobs and machines. We generally use $i$ as index for machines, and
$j$ as index for jobs.

Mixed-Integer Linear Programs. The set of feasible solutions of any MILP is

$\displaystyle\mathcal{Q}\coloneqq\left\\{\bm{x}\in\mathbb{Z}_{\geq
0}^{n},\bm{y}\in\mathbb{R}_{\geq 0}^{r}\mid\begin{pmatrix}A&B\\\
0&C\end{pmatrix}\cdot\begin{pmatrix}\bm{x}\\\
\bm{y}\end{pmatrix}=\bm{b}\right\\}$ (MILP)

for matrices $A\in\mathbb{Z}^{m\times n}$, $B\in\mathbb{Z}^{m\times
r},C\in\mathbb{Z}^{s\times r}$ and a vector $\bm{b}\in\mathbb{Z}^{m+s}$. The
encoding size $\langle\mathit{MILP}\rangle$ of (MILP) is logarithmic in the
largest coefficient $\Delta\coloneqq\max_{i,j}|A_{i,j}|$ and right-hand side,
but linear in the number of variables and constraints.

We will make use of the following classical result for finding solutions of
(MILP), which was proved first by Lenstra [41] and obtained with improved run
time by Kannan [37].

######  Proposition 10 (Kannan [37]).

For any instance of (MILP), in time
$2^{\mathcal{O}(n\log(n))}\langle\mathit{MILP}\rangle^{\mathcal{O}(1)}$ one
either finds a solution $(\bm{x},\bm{y})\in\mathcal{Q}$ or determines that
$\mathcal{Q}=\emptyset$.

In the following, we reproduce two useful lemmata about the structure of
(MILP) solutions, which are inherited from its integral and fractional parts.

######  Lemma 11.

For any instance of (MILP) and any
$(\hat{\bm{x}},\hat{\bm{y}})\in\mathcal{Q}$, in time
$\langle\mathit{MILP}\rangle^{\mathcal{O}(1)}$ we can find
$(\hat{\bm{x}},\tilde{\bm{y}})\in\mathcal{Q}$ such that $\tilde{\bm{y}}$ is a
vertex solution of the following restricted LP:

$\displaystyle\left\\{\bm{y}\in\mathbb{R}_{\geq 0}^{r}\mid\begin{pmatrix}B\\\
C\end{pmatrix}\cdot\bm{y}=\bm{b}-\begin{pmatrix}A\\\
0\end{pmatrix}\cdot\hat{\bm{x}}\right\\}\enspace.$ (R-LP)

######  Lemma 12.

For any instance of (MILP) and any $(\hat{\bm{x}},\hat{\bm{y}})\in\mathcal{Q}$
there is some $(\tilde{\bm{x}},\hat{\bm{y}})\in\mathcal{Q}$ such that
$\tilde{\bm{x}}$ has minimum-cardinality support
$|\operatorname{supp}(\bm{x})|$ of all solutions $\bm{x}$ to the restricted
ILP

$\displaystyle\left\\{\bm{x}\in\mathbb{Z}_{\geq 0}^{n}\mid\begin{pmatrix}A\\\
0\end{pmatrix}\cdot\bm{x}=\bm{b}-\begin{pmatrix}B\\\
C\end{pmatrix}\cdot\hat{\bm{y}}\right\\}\enspace.$ (R-ILP)

Importantly, this implies that _any_ support size bound for an ILP can be
directly applied to the integer variables of an MILP. One of these
applications is an algorithm to solve MILPs with few constraints. This was
presented explicitly and analyzed in terms of $m$ and $\Delta$ by Rohwedder
and Verschae [48, p. 30]. As we will make extensive use of it, we formulate
the underlying idea in the following lemma.

######  Lemma 13.

For any instance of (MILP) and any $s\leq n$, in time
$2^{\mathcal{O}(s\log(n))}\cdot\langle\mathit{MILP}\rangle^{\mathcal{O}(1)}$
we either find a solution $\bm{x}$ of minimum-cardinality support such that
$(\bm{x},\bm{y})\in\mathcal{Q}_{\leq
s}\coloneqq\\{(\bm{x},\bm{y})\in\mathcal{Q}\colon|\operatorname{supp}(\bm{x})|\leq
s\\}$, or determine that $\mathcal{Q}_{\leq s}=\emptyset$

###### Proof.

We exhaustively try all choices of $\operatorname{supp}(\bm{x})$, which are
$\binom{n}{s}\leq n^{s}$ candidates, from $|\operatorname{supp}(\bm{x})|=0$ up
to $s$. For each choice we restrict (MILP) to $\operatorname{supp}(\bm{x})$,
by fixing all other integer variables to $0$. With Proposition 10 we either
find a solution with $s$ integral variables, or determine the infeasibility,
in time $s^{\mathcal{O}(s)}\langle\mathit{MILP}\rangle^{\mathcal{O}(1)}$. The
claimed run time follows from that $s\leq n$. ∎

Note that a support size bound $s$ on any solution of (R-ILP) allows us to use
Lemma 13 to find a solution with support size $s$, or decide the infeasibility
of the entire (MILP). Lemma 13 directly extends to optimizing a linear
objective function; and to finding a non-zero solution of minimum-cardinality
support, which might be of interest for augmentation algorithms.

Approximation Guarantees. Ultimately, we want to guarantee that our solution
has a value that is within a factor $(1+\varepsilon)$ of the optimum. As we
approximate in multiple places, we distribute this factor through the use of a
linear auxiliary variable $\delta=\varepsilon/c$. The value of $c$ only
depends on the algorithm, not the input, and we can use
$\mathcal{O}$-techniques for $\delta\searrow 0$ to ensure its existence. I.e.,
adding constantly many errors of $\delta$ constantly many times still has an
approximation guarantee of
$(1+\mathcal{O}(\delta))^{\mathcal{O}(1)}=1+\mathcal{O}(\delta)$.

We approximate by rounding input quantities, to reduce the number of distinct
machine speeds and job processing times, and by over-allocating some machines
by a limited amount. The direction of rounding is irrelevant here. Rounding
towards a harder instance (i.e., one with larger jobs and slower machines)
increases the makespan. When rounding towards a simpler instance (i.e., one
with smaller jobs and faster machines), the makespan needs to be increased to
maintain consistency. Hence, either way, the makespan increases by the same
asymptotic amount.

Scheduling Problems. An instance $\mathcal{I}$ of $Q||C_{\max}$ consists of a
set $\mathcal{J}$ of $N$ _jobs_ with processing times $p_{1}\leq\ldots\leq
p_{N}$, and a set $\mathcal{M}$ of $M$ _machines_ with speeds
$s_{1}\leq\ldots\leq s_{M}$. In the simpler $P||C_{\max}$ setting, all
machines are identical, and consequently run at unit speed, i.e.,
$s_{1}=\ldots=s_{M}=1$.

A _schedule_ $\sigma\colon\mathcal{J}\to\mathcal{M}$ assigns jobs to machines.
For each machine $i\in\mathcal{M}$ the set of jobs that are assigned to $i$ by
$\sigma$ is $\sigma^{-1}(i)$. The _completion time_ of a machine
$i\in\mathcal{M}$ is
$C_{i}^{(\sigma)}\coloneqq\sum_{j\in\sigma^{-1}(i)}p_{j}/s_{i}$; the
completion times of the machines form the vector $\bm{C}^{(\sigma)}$. A
schedule’s _makespan_ is $C_{\max}^{(\sigma)}$, the largest completion time.
We will generally omit the schedule $\sigma$ in the notation. The objective of
our scheduling problems is to find schedules which minimize the makespan
$C_{\max}$; let
$\operatorname{OPT}(\mathcal{I})=\min_{\sigma}C_{\max}^{(\sigma)}$ be the
optimal makespan of instance $\mathcal{I}$. For any $\alpha\geq 1$, an
$\alpha$-approximate schedule for $\mathcal{I}$ is a schedule of makespan at
most $\alpha\cdot\operatorname{OPT}(\mathcal{I})$.

Run Time Analysis. We use $\mathcal{O}$-identities specific to the analysis of
EPTAS run times $2^{\mathcal{O}(f(1/\varepsilon))}+N^{\mathcal{O}(1)}$. For
our algorithms we have $f(1/\varepsilon)\in\mathcal{O}(1/\varepsilon^{2})$ and
can therefore use $\log(N)\in\mathcal{O}(1/\varepsilon^{2})$ when analyzing
terms logarithmic in $N$, as otherwise $\mathcal{O}(N)$ dominates the run
time. The inequality $a\cdot b\leq a^{2}+b^{2}$ implies that
$2^{\mathcal{O}(1/\varepsilon)}\cdot\log^{\mathcal{O}(1)}(N)=2^{\mathcal{O}(1/\varepsilon)}+\log^{\mathcal{O}(1)}(N)$.
Because of $\log^{\mathcal{O}(1)}(N)\subset\mathcal{O}(N)$, this gives us
another way to eliminate run time factors logarithmic in $N$. Further, as
$\log(1+x)\geq x$ for $0\leq x\leq 1$ (in base 2), it holds that
$\log_{1+\varepsilon}(\cdot)=\log(\cdot)/\log(1+\varepsilon)\in\mathcal{O(\log(\cdot)/\varepsilon})$.

##  3 Refined Support Size Bounds for Integer Linear Programs

In this section, we refine the general support size bounds independent of $n$
for integer programs. Previous such bounds used as parameters the number of
constraints $m$, and the largest absolute value $\Delta$ of an entry in the
constraint matrix $A$. In our MILP formulation for $Q||C_{\max}$, we bound the
support size by the _maximum $1$-norm_ of a column vector, denoted by
$A_{\max}\coloneqq\max_{i=1,\ldots,n}\|A_{i}\|_{1}$. Clearly, $\Delta\leq
A_{\max}\leq m\cdot\Delta$ holds, but it also means that support size bounds
using only $m$ and $\Delta$ are too coarse for some ranges. Instead, we will
show bounds using only $m$ and $A_{\max}$.

In the following, let $\mathcal{P}=\\{\bm{x}\in\mathbb{R}^{n}_{\geq 0}\mid
A\bm{x}=\bm{b}\\}$ for $A\in\mathbb{Z}^{m\times n}$ be a polytope and
$\mathcal{P}_{I}=\text{Conv}(\mathcal{P}\cap\mathbb{Z}^{n})$ be the convex
hull of the integer points of $\mathcal{P}$. For simplicity, we only consider
feasible ILPs $\mathcal{L}\neq\emptyset$ with $\operatorname{rank}(A)=m$ in
this section. Recall that every ILP
$\mathcal{L}\coloneqq\max\\{\bm{c}^{\intercal}\bm{x}\mid\bm{x}\in\mathcal{P}_{I}\\}$
with an optimal solution also has an optimal vertex solution
$\bm{v}\in\mathcal{P}_{I}$. Let $S\coloneqq\operatorname{supp}(\bm{v})$ be the
support of the vertex solution $\bm{v}$, and $s\coloneqq|S|$ the size of the
support.

Our results are based on a bound by Aliev et. al [2]. We omit the inverse of
the $\gcd$ of all submatrix determinants $g^{-1}$ from their result, as it is
$1$ for almost all matrices.

######  Proposition 14 (Aliev et. al. [2, Thm. 1(2)]).

Any ILP $\mathcal{L}$ with constraint matrix $A\in\mathbb{Z}^{m\times n}$ has
an optimal solution $\bm{v}\in\mathcal{L}$ with support size
$|\operatorname{supp}(\bm{v})|=s\leq m+\log(\sqrt{\det(A\cdot A^{T})})$.

In this form, the determinant of the support size bound can depend on $n$. The
strength of Proposition 14 is the ability to restrict $A$ to the columns with
non-zero variables. For our vertex solution $\bm{v}$ with support
$S=\operatorname{supp}(\bm{v})$, this is exactly $A_{S}$, the columns of the
variables in the support. Aliev et al. [2] used the inequality
$\sqrt{\det(A_{S}\cdot A_{S}^{T})}\leq(\sqrt{s}\Delta)^{m}$ to ultimately
obtain the support size bound $s\leq 2m\log(2\sqrt{m}\Delta)$ [1, Theorem
1(ii)]. We analyze the term $\det(A_{S}\cdot A_{S}^{T})$ with regard to the
more fine-grained parameter $A_{\max}$ to obtain a tighter bound:

######  Lemma 15.

For any matrix $A_{S}\in\mathbb{Z}^{m\times s}$ it holds that
$\sqrt{\det(A_{S}\cdot A_{S}^{T})}\leq(\sqrt{s/m}\cdot A_{\max})^{m}$.

###### Proof.

The matrix $G\coloneqq A_{S}\cdot A_{S}^{T}$ is symmetric and positive semi-
definite. If $G$ has an eigenvalue of $0$ then $\det(G)=0$ and the inequality
holds. We will thus assume that $G$ is positive definite, i.e., all
eigenvalues are positive. It is a classical result that for positive definite
matrices, the Hadamard inequality can be strengthened to
$\det(G)\leq\prod_{i=1}^{m}G_{i,i}$, the product of the diagonal entries
$G_{i,i}$. We refer to a modern presentation by Browne et al. [11, Thm. 2] for
this fact. As $G=A_{S}\cdot A_{S}^{T}$, it is sufficient to bound
$\varphi(A_{S})\coloneqq\prod_{i=1}^{m}\sum_{j=1}^{s}A_{S;i,j}^{2}$ subject to
$\sum_{i=1}^{m}|A_{S;i,j}|\leq A_{\max}$ for $j=1,\ldots,s$ by $(s/m\cdot
A_{\max}^{2})^{m}$ to obtain our result. We will first characterize a matrix
$A_{S}$ such that $\varphi(A_{S})$ is maximal and then relate $\varphi(A_{S})$
to $(s/m\cdot A_{\max}^{2})^{m}$. As all entries $A_{S;i,j}$ of $A_{S}$ occur
as squares or absolute values in the optimization, we can assume
$A_{S;i,j}\geq 0$ in the following. As $\varphi$ is monotone in each variable,
the matrix $A_{S}$ that maximizes $\varphi(A_{S})$ under the condition
$\sum_{i=1}^{m}|A_{S;i,j}|\leq A_{\max}$ will fulfill these constraints with
equality, i.e., $\sum_{i=1}^{m}|A_{S;i,j}|=A_{\max}$ for $j=1,\ldots,s$.
Renaming $A_{S;i,j}$ to $x_{i,j}$ thus gives us the optimization problem:

$\displaystyle\max\prod_{i=1}^{m}\sum_{j=1}^{s}x_{i,j}^{2}\quad\text{s.t.}\;\sum_{i=1}^{m}x_{i,j}=A_{\max}\quad
x_{i,j}\geq 0\quad\operatorname{for}\;i=1,\ldots,m;j=1,\ldots,s\enspace.$

To bound the optimal solutions to this program, we first consider optimal
solutions over the same region with objective function
$\sum_{i=1}^{m}\sum_{j=1}^{s}x_{i,j}^{2}$. This is a convex objective function
over a polyhedral region. Bauer’s maximum principle implies that the maximum
is assumed at a vertex and thus has $s$ non-zero variables [6]. Consequently,
we have $\sum_{i=1}^{m}\sum_{j=1}^{s}x_{i,j}^{2}\leq s\cdot A_{\max}^{2}$.
Now, consider the problem of maximizing $\max\prod_{i=1}^{m}y_{i}$ with
$\sum_{i=1}^{m}y_{i}\leq s\cdot A_{\max}^{2}$ and $y_{i}\geq 0$. The logarithm
is monotone, so we can apply it to the objective, giving
$\sum_{i=1}^{m}\log(y_{i})$ instead. For any solution $x^{*}_{i,j}$ maximizing
$\sum_{i=1}^{m}\sum_{j=1}^{s}x_{i,j}^{2}$, we can compute the $y^{*}_{i}$ with
$y^{*}_{i}=\sum_{j=1}^{s}{x^{*}_{i,j}}^{2}$ that will maximize
$\sum_{i=1}^{m}\log(y_{i})$. As the logarithm is concave, we can thus maximize
$\sum_{i=1}^{m}\log(y_{i})$ by $y^{*}_{1}=\ldots=y^{*}_{m}=s/m\cdot
A_{\max}^{2}$, as we could otherwise improve a solution by re-balancing it.
Hence, $\varphi(A_{S})\leq(s/m\cdot A_{\max}^{2})^{m}$, which implies our
inequality. ∎

Importantly, by substituting $A_{\max}$ with $\sqrt{m}\Delta$, our inequality
in Lemma 15 becomes the one used by Aliev et. al. [2]. Therefore, any of the
following results can also be obtained for $\sqrt{m}\Delta$ instead of
$A_{\max}$. Proposition 14 and Lemma 15 imply the essential intermediate
result:

######  Corollary 16.

Any ILP $\mathcal{L}$ with constraint matrix $A\in\mathbb{Z}^{m\times n}$ has
an optimal solution $\bm{v}\in\mathcal{L}$ with
$|\operatorname{supp}(\bm{v})|=s$ such that $s/m\leq 1+\log(\sqrt{s/m}\cdot
A_{\max})=1+\log(A_{\max})+\log(s/m)/2$.

The proof of Proposition 14 uses Siegel’s Lemma, a deep result from
transcendental number theory. In contrast, Berndt et. al. [7] derive a support
size bound of the same form using only elementary methods, but with worse
constants. Building on their approach, we also derived a bound, which is
slightly weaker than Corollary 16, but requires only elementary combinatorial
arguments.

######  Lemma 17.

Any ILP $\mathcal{L}$ with constraint matrix $A\in\mathbb{Z}^{m\times n}$ has
an optimal solution $\bm{v}\in\mathcal{L}$ with
$|\operatorname{supp}(\bm{v})|=s$ such that $s/m\leq
1+\log(e)+\log(1+(s/m)\cdot A_{\max})$.

Unfortunately, both sides of Corollary 16 are still dependent on $s$. We
resolve Corollary 16 for $s$ in two ways, both parametric in the trade-off
between constant and growing terms. In the first approach, we bound the
logarithm by its tangents.

######  Lemma 18.

For any $\alpha>0$ and $x>0$, it holds $\log(x)\leq\alpha\cdot
x-\log(e)+\log(\log(e)/\alpha)$.

###### Proof.

At $x=\log(e)/\alpha$, both sides are equal to $\log(\log(e)/\alpha)$, and the
derivatives are $\alpha$. Hence, the affine function of the right-hand side is
an upper bound on the left-hand side, as $\log(x)$ is concave. ∎

This direct approach allows us to give simple and short formulas for the
bounds.

######  Theorem 19.

For any $\alpha\in(0,1)$ there is an optimal solution $\bm{v}$ of ILP with

$\displaystyle s\leq m\cdot\log(\sqrt{2\log(e)/(e\cdot\alpha)}\cdot
A_{\max})/(1-\alpha)\enspace.$

###### Proof.

Applying Lemma 18 with $2\alpha$ to Corollary 16 yields

$\displaystyle s/m$ $\displaystyle\leq 1+\log(A_{\max})+(2\alpha\cdot
s/m-\log(e)+\log(\log(e)/(2\alpha)))/2$
$\displaystyle\leq\log(\sqrt{2\log(e)/(e\cdot\alpha)}\cdot
A_{\max})+\alpha\cdot s/m\enspace.$

We subtract $\alpha\cdot s/m$, and multiply by $m/(1-\alpha)$, which proves
the claim for $0<\alpha<1$. ∎

For example, we can set $\alpha=1/2$ or $\alpha=1/11$ to obtain the bounds
$s\leq 2m\cdot\log(1.46\cdot A_{\max})$ and $s\leq 1.1m\cdot\log(3.42\cdot
A_{\max})$.

This approach, however, only gives bounds with coefficient strictly larger
than $1$ for the leading term. To reduce this to $1$, we make use of advanced
analytical function techniques, to tighter analyze the inequality of Corollary
16.

######  Lemma 20.

For $s,m,A_{\max}\geq 1$, the inequality in Corollary 16 is equivalent to

$\displaystyle
s/m\leq-\log(e)\cdot\mathcal{W}_{-1}(-1/(2\log(e)A_{\max}^{2}))/2,$

where $\mathcal{W}_{-1}$ is the $-1$ branch of the LambertW-function, the
inverse function of $x\mapsto xe^{x}$.

###### Proof.

We substitute $s/m$ by $-\log(e)\cdot y/2$, and rearrange to obtain:

$\displaystyle-\log(e)\cdot y/2$ $\displaystyle\leq
1+\log(A_{\max})+\log(-\log(e)\cdot y/2)/2$ $\displaystyle\log(-\log(e)\cdot
y)+\log(e)\cdot y$
$\displaystyle\geq-(2+2\log(A_{\max})-1)=-1-2\log(A_{\max})$
$\displaystyle-\log(e)\cdot y\cdot 2^{\log(e)\cdot y}$ $\displaystyle\geq
1/(2\cdot A_{\max}^{2})\Leftrightarrow y\cdot e^{y}\leq-1/(2\log(e)\cdot
A_{\max}^{2}).$

For the right-hand side $z\coloneqq-1/(2\log(e)\cdot A_{\max}^{2})$, we have
$-1/e\leq-1/(2\log(e))\leq z\leq 0$. Therefore, the inequality is satisfied
exactly when $\mathcal{W}_{-1}(z)\leq y\leq\mathcal{W}_{0}(z)$ holds, where
$\mathcal{W}_{k}$ are the real branches of the aforementioned LambertW-
function.

Next, we show $y\leq\mathcal{W}_{0}(z)$ does not restrict any relevant values.
For $x\in[{-1/e},0]$, we have $W_{0}(x)\geq e\cdot x$. Furthermore $s/m\cdot
A_{\max}^{2}\geq 1\geq e/4$ holds for the relevant values of $s/m\geq 1$ and
$A_{\max}\geq 1$. Therefore
$\mathcal{W}_{0}(z)\geq-e/(2\log(e)A_{\max}^{2})\geq-2\cdot(s/m)/\log(e)=y$.
This shows that the positive solutions are only constrained from above, by
$\mathcal{W}_{-1}(z)$. Applying the resubstitution of $y$ to its lower bound
gives the claimed result. ∎

Now, we apply techniques analogous to Chatzigeorgiou [12] to prove parametric
bounds for the $\mathcal{W}_{-1}(z)$ branch, which we optimize for
$z\rightarrow 0$ instead of $z\rightarrow-1/e$.

######  Lemma 21.

For any $\alpha>0$ and $u\geq 0$, it holds $-\mathcal{W}_{-1}(-e^{-u-1})\leq
u+\sqrt{2\alpha\cdot u}+\alpha-\ln(\alpha)$.

###### Proof.

Chatzigeorgiou [12] showed for $x=-\mathcal{W}_{-1}(-e^{-u-1})-1$ that
$g(x)=u$, where $g(x)\coloneqq x-\ln(1+x)$. To show our result, it thus
suffices to show that for all $x\in\mathbb{R}>0$ and some additive term
$\beta$, only dependent on $\alpha$, it holds that

$\displaystyle-\mathcal{W}_{-1}(-e^{-u-1})=x+1\leq g(x)+\sqrt{2\alpha\cdot
g(x)}+\beta+1=u+\sqrt{2\alpha\cdot u}+\beta+1\enspace.$

By definition of $g$, this reduces to showing
$f(x)\coloneqq-\ln(1+x)+\sqrt{2\alpha\cdot(x-\ln(1+x))}+\beta\geq 0$. The
function $f$ has a unique minimum, since we will show that $f^{\prime}(x)=0$
has only one solution and $\lim_{x\rightarrow\infty}f(x)=\infty$. Consider the
critical condition:

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}x}f(x)=\frac{-1}{1+x}+\frac{(1-\frac{1}{1+x})\cdot\alpha}{\sqrt{2\alpha(x-\ln(1+x))}}=0\quad\Leftrightarrow\quad\frac{x\alpha}{\sqrt{2\alpha(x-\ln(1+x))}}=1\enspace.$
(1)

Equation 1 can not be solved for $x$ directly. Instead, we show that there can
be only one solution, a global minimum, because the second derivative of
$f(x)$ is always positive, making $f(x)$ monotonously increasing.

$\frac{\mathrm{d}}{\mathrm{d}x^{2}}f(x)=\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{\alpha
x}{\sqrt{2\alpha(x-\ln(1+x))}}-1\right)=\frac{-x(1-\frac{1}{1+x})\alpha^{2}}{(2\alpha(x-\ln(1+x)))^{3/2}}+\frac{\alpha}{\sqrt{2\alpha(x-\ln(1+x))}}>0\quad\Leftrightarrow\\\
\frac{-\alpha^{2}x^{2}/(1+x)}{2\alpha(x-\ln(1+x))}+\alpha>0\quad\Leftrightarrow\quad\frac{x^{2}}{1+x}<2(x-\ln(1+x))\quad\Leftrightarrow\quad\frac{x(2+x)}{2(1+x)}\geq\ln(1+x)$

We know Equation 1 must hold at the global minimum. Hence, substituting it in
the inequality $f(x)\geq 0$ and applying Lemma 18 on $\ln(1+x)$ bounds the
minimal value of $f(x)$ by

$f(x)=-\ln(1+x)+\alpha x+\beta\geq-\alpha(1+x)-\ln(1/\alpha)+1+\alpha
x+\beta\geq
0\quad\Leftrightarrow\quad\beta\geq\alpha+\ln(1/\alpha)-1\enspace.$

We conclude that $-\mathcal{W}_{-1}(-e^{-u-1})\leq u+\sqrt{2\alpha\cdot
u}+\alpha+\ln(1/\alpha)$, which is the claim. ∎

From Lemma 20 and Lemma 21 we derive our asymptotically tight support size
bound.

######  Theorem 22.

For any $\alpha^{\prime}>0$ there is an optimal solution $\bm{v}$ of ILP with

$\displaystyle s\leq
m\cdot(\log(A_{\max})+\sqrt{\alpha^{\prime}(\log(A_{\max})+0.05)}+\alpha^{\prime}/2+\log(\sqrt{1/\alpha^{\prime}})+1.03)\enspace.$

###### Proof.

We need to rewrite the argument $z\coloneqq-1/(2\log(e)A_{\max}^{2})$ in Lemma
20 to the form $-e^{-u-1}$ used in Lemma 21. Hence, solving $z=-e^{-u-1}$
gives $u=\ln(2\log(e)A_{\max}^{2}/e)=2\ln(A_{\max})+\ln(2\log(e)/e)$. We now
substitute $\alpha$ by $\alpha^{\prime}/\log(e)$ to get $\log$ instead of
$\ln$, and through calculation obtain the bound:

$\displaystyle s/m$
$\displaystyle\leq-\log(e)\mathcal{W}_{-1}(z)/2\leq\log(e)(u+\sqrt{2\alpha\cdot
u}+\alpha-\ln(\alpha))/2$
$\displaystyle\leq\log(e)(u+\sqrt{2\alpha^{\prime}/\log(e)\cdot
u}+\alpha^{\prime}/\log(e)-\ln(\alpha^{\prime}/\log(e)))/2$
$\displaystyle\leq\log(e)u/2+\sqrt{\log(e)\alpha^{\prime}u/2}+\alpha^{\prime}/2-\log(\alpha^{\prime}/\log(e))/2$
$\displaystyle\leq\log(A_{\max})+\log(2\log(e)/e)/2+\sqrt{\log(e)\alpha^{\prime}u/2}-\log(\alpha^{\prime}/\log(e))/2+\alpha^{\prime}/2$
$\displaystyle\leq\log(A_{\max})+\sqrt{\alpha^{\prime}(\log(A_{\max})+\log(2\log(e)/e)/2)}+\alpha^{\prime}/2+\log(\log(e)\sqrt{2/(e\alpha^{\prime})})\enspace.$

Inserting numerical values for terms independent of $\alpha^{\prime}$ and
$A_{\max}$ gives the desired result. ∎

For $\alpha=1$ and $A_{\max}\geq 1$ we obtain the particularly simple bounds

$s\leq m\cdot(\log(A_{\max})+\sqrt{\log(A_{\max})+0.05}+1.53)\leq
m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})\enspace.$

This immediately implies our main support size bound: See 2 The results of
this section directly extend to other $p$-norm bounds on the column vectors of
$A$:

######  Corollary 23.

Let $A_{\max}^{(p)}\coloneqq\max_{i}\|A_{i}\|_{p}$ be the largest $p$-norm of
columns of $A$ for $p\geq 1$. It holds that

$\displaystyle\log(A_{\max})\leq\log(m^{1-1/p}A_{\max}^{(p)})\quad\text{and}\quad\log(A_{\max})\leq
p\cdot\log(A_{\max}^{(p)})\enspace.$

In order to understand how tight our bound is, we adapt a construction by
Berndt et. al. [7] to obtain a lower bound on the support size and close the
asymptotic gap. See 3

###### Proof.

With $d\coloneqq\lfloor\log(A_{\max})\rfloor$ we construct an ILP as follows:

$\displaystyle\max$
$\displaystyle\;\,\begin{pmatrix}3^{0}&\cdots&3^{d}&3^{0}&\cdots&3^{d}&\cdots&3^{0}&\cdots&3^{d}\end{pmatrix}$
s.t. $\displaystyle\begin{pmatrix}2^{0}&\cdots&2^{d}&0&&&\cdots&&&0\\\
0&\cdots&0&2^{0}&\cdots&2^{d}&\cdots&0&\cdots&0\\\ &\vdots&&&&&&\ddots&\\\
0&&&\cdots&&&0&2^{0}&\cdots&2^{d}\end{pmatrix}=\begin{pmatrix}2^{d+1}-1\\\
2^{d+1}-1\\\ \vdots\\\ 2^{d+1}-1\end{pmatrix}\enspace.$

Because of $\sum_{i=0}^{d}2^{i}=2^{d+1}-1$, the $\bm{1}$-vector is a solution.
All coefficients are positive, hence in any solution the value of the
variables with coefficient $2^{d}$ must be less than $2$. For any other
variable $x_{1}$, if it is $x_{i}\geq 2$, we can increase the objective by
setting $x_{i}\coloneqq x_{i}-2;x_{i+1}\coloneqq x_{i+1}+1$. Since all
objective coefficients are positive, the $\bm{1}$-vector is the unique optimal
solution. ∎

Hence, Theorem 22 is exact in the dominant term. We pose the question, whether
there is a support size bound of the form $m\cdot\log(c\cdot A_{\max})$ for
some constant $c$, as an interesting open problem.

##  4 An Efficient Approximation Scheme for Makespan Minimization on Uniformly
Related machines

Our algorithm follows a typical structure of approximation schemes. First, we
_preprocess_ the input, by discarding jobs and machines which are so short or
slow that assigning them naively is acceptable. Next, we perform a _binary
search_ on the makespan, to reduce the optimization problem to a feasibility
problem. Then, we _round_ the remaining processing times and machine speeds,
according to our makespan guess, to make the resulting instance more
structured. Now, we _construct_ an MILP, whose feasibility is equivalent to
the existence of a schedule. Finally, we solve the MILP and _transform_ the
solution into a schedule.

###  4.1 Preprocessing

We reduce the number of parameters bounding the instance to the number of jobs
$N$ and a constant fraction $\delta$ of the approximation guarantee
$\varepsilon$. To enforce $N\geq M$ we potentially drop the $M-N$ slowest
machines, as there is an optimal solution not assigning them a job.

##### Step 1: Removing Negligible Machines and Jobs

We remove all machines slower than $\delta\cdot s_{\max}/N$ and all jobs
shorter than $\delta\cdot p_{\max}/N$. Compensating for the lost processing
times on a longest job and the machine speeds on a fastest machine introduces
an error of at most a factor $(1+\delta)$ respectively. Now we have
$p_{\min}>\delta\cdot p_{\max}/N$ and $s_{\min}>\delta\cdot s_{\max}/N$ and
the largest ratios of job processing times $p_{\max}/p_{\min}<N/\delta$ and
machine speeds $s_{\max}/s_{\min}<N/\delta$ are bounded only by the parameters
$N$ and $\delta$.

##### Step 2: Preround the Inputs

To achieve a linear run time, we preround the machine speeds and processing
times to fewer distinct values. These are rerounded again more carefully at
every iteration of the binary search, reducing the run time at the cost of a
limited accuracy loss. We round every processing time $p_{j}$ and machine
speed $s_{i}$ down to the next power of $(1+\delta)$, introducing errors of no
more than $(1+\delta)$ by construction. Let $\tilde{\eta}_{j}$ be the number
of jobs with rounded processing times $\tilde{p}_{j}$ be and $\tilde{\mu}_{i}$
the number of machines with rounded speed $\tilde{s}_{j}$. Due to step 1, the
amount of _distinct_ values after rounding is bounded by
$\log_{1+\delta}(p_{\max}/(p_{\max}\delta/N))=\log_{1+\delta}(s_{\max}/(s_{\max}\delta/N))\in\mathcal{O}(1/\delta\log(1/\delta\cdot
N))$. Because our inputs are sorted, the rounding above can be performed in
time $\mathcal{O}(N+1/\delta\log(1/\delta\cdot N))$.

##### Step 3: Binary Search for the Makespan

We reduce finding the optimal makespan $\operatorname{OPT}(\mathcal{I})$ to
successively checking whether a schedule with makespan $T$ is realizable. The
processing time of a longest job on a fastest machine is a lower bound:
$\operatorname{OPT}(\mathcal{I})\geq p_{\max}/s_{\max}$. The schedule
assigning all jobs to a fastest machine is an upper bound
$\operatorname{OPT}(\mathcal{I})\leq\sum_{j=1}^{N}p_{i}/s_{\max}\leq
Np_{\max}/s_{\max}$. Hence, we can use a binary search for
$\operatorname{OPT}(\mathcal{I})$ in the interval $[p_{\max}/s_{\max},N\cdot
p_{\max}/s_{\max}]$ of ratio $N$. As accuracy up to a factor $(1+\delta)$ is
sufficient, we only need to consider integer powers of $(1+\delta)$. Our
binary search therefore adds a factor of
$\mathcal{O}(\log_{1+\delta}(N))=\mathcal{O}(1/\delta\log(N))$ to the run time
of the following steps. We denote the current makespan in the binary search by
$T$. This transforms the problem into either finding a schedule with makespan
$(1+\mathcal{O}(\delta))\cdot T$, or deciding that no schedule with makespan
$T$ exists.

##### Step 4: Rounding Machine Speeds and Job Processing Times

A $(1+\varepsilon)$-approximate schedule $\sigma$ satisfies, for each machine
$i$, the equivalent inequalities

$\sum_{j\in\sigma^{-1}(i)}\frac{p_{j}}{s_{i}}\leq(1+\varepsilon)\cdot
T\quad\Leftrightarrow\quad\sum_{j\in\sigma^{-1}(i)}\frac{p_{j}}{T}\leq(1+\varepsilon)\cdot
s_{i}\enspace.$ (2)

With the aforementioned bounds on the makespan we have enforced the descending
chain

$\displaystyle s_{\max}\geq p_{\max}/T\geq p_{\min}/T>\delta\cdot
p_{\max}/(N\cdot T)\geq\delta s_{\max}/N^{2}\enspace.$

Therefore, all quantities are in the interval $I\coloneqq(\delta\cdot
s_{\max}/N^{2},s_{\max}]$ of ratio $N^{2}/\delta$, especially the scaled
processing times $p_{j}/T$. See also Figure 1 for an overview on the relations
of the parameters. We now scale each processing time $p_{j}$ with $1/T$; this
yields an instance with scaled processing times $\tilde{p}_{j}=1/T\cdot
p_{j}$, equivalent to our original instance by Equation 2.

$T$$s_{\mathrm{max}}\delta/N^{2}$$p_{\mathrm{max}}\delta/(N\cdot
T)$$s_{\mathrm{max}}\delta/N$$s_{\mathrm{max}}$$p_{\mathrm{max}}/T$

Figure 1: Overview on the range of parameters.

The crucial innovation by Berndt, Deppert, Jansen and Rohwedder [8] was to
combine exponential and linear rounding to obtain both sufficient accuracy
with few values and useful structural properties. We adapt their approach to
cover our interval $I$. With $\kappa\coloneqq\lceil\log(1/\delta\cdot
N^{2})\rceil$, consider the points $b_{k,0}\coloneqq s_{\max}\cdot 2^{-k}$ for
$k=0,\ldots,\kappa$. The intervals $[b_{k+1,0},b_{k,0}]$ become exponentially
finer, but have a ratio of $2$, not the necessary $(1+\delta)$. Therefore,
with $\lambda\coloneqq\lceil 1/\delta\rceil$, we add the points
$b_{k,\ell}\coloneqq(1-\ell/(2\lambda))\cdot b_{k,0}$ for
$k=0,\ldots,\kappa-1$ and $\ell=0,\ldots,\lambda$, which is a linear
interpolation between $b_{k,0}$ and $b_{k+1,0}$. Simple calculations show the
relations $b_{k,\ell-1}/b_{k,\ell}=1+1/(2\lambda-\ell)\leq 1+\delta$ and
$b_{k+1,0}=b_{k,0}/2=b_{k,\lceil 1/\delta\rceil}$ for all
$k=0,\ldots,\kappa-1$ and $\ell=1,\ldots,\lambda$, which means we have
achieved the necessary precision. Crucially, two jobs within a linear interval
of the same parity combine exactly to a job in the next larger linear
interval. Formally, this is described by

$\displaystyle
b_{k,\ell}+b_{k,\ell^{\prime}}=\left(2-\frac{\ell+\ell^{\prime}}{2\lambda}\right)\cdot
b_{k,0}=\left(1-\frac{\frac{\ell+\ell^{\prime}}{2}}{2\lambda}\right)\cdot
b_{k-1,0}=b_{k-1,\frac{\ell+\ell^{\prime}}{2}}$ (3)

for all $0\leq\ell\leq\ell^{\prime}\leq\lambda$ with $\ell+\ell^{\prime}$
divisible by $2$, i.e., $\ell$ and $\ell^{\prime}$ are both odd or both even.
Equation 3 will allow us to significantly reduce the number of configurations
and the maximum $1$-norm of a column. To simplify our notations, we re-index
the values of $b_{k,\ell}$ in descending order by setting $b_{r}\coloneqq
b_{k(r),\ell(r)}$ with $k(r)=\lfloor(r-1)/\lambda\rfloor$ and
$\ell(r)=(r-1)\bmod\lambda$, such that $b_{k\cdot\lambda+\ell+1}=b_{k,\ell}$.
Therefore, the interval $I$ is covered completely by the
$\tau\coloneqq\kappa\cdot\lambda\in\mathcal{O}(1/\delta\log(1/\delta\cdot N))$
intervals $(b_{r+1},b_{r}]$ for $r=1,\ldots,\tau$. Finally, we round every
machine speed $\tilde{s}_{i}$ as well as every scaled processing time
$\tilde{p}_{j}$ in $(b_{r+1},b_{r}]$ up to $b_{r}$. Let $\mu_{i}$ and
$\eta_{j}$ be the number of machines with scaled speed $b_{i}$ and jobs with
scaled processing time $b_{j}$ respectively. This takes time
$\mathcal{O}(1/\delta\log(1/\delta\cdot N))$, which means steps 1 to 4 can be
performed in total time

$\mathcal{O}(N+1/\delta\log(N)(1/\delta\log(1/\delta\cdot
N)+\tau))=\mathcal{O}(N+1/\delta^{2}\log^{2}(1/\delta\cdot
N))\subseteq\mathcal{O}(1/\delta^{2+2\cdot 2})+\mathcal{O}(N)\enspace.$

Figure 2 contains a graphical representation of the exponential intervals
$[b_{k+1,0},b_{k,0}]$ and the linear sub-intervals $[b_{k,i+1},b_{k,i}]$.

$\vdots\phantom{b_{2,0}}\;\,$$b_{9}=b_{2,0}$$b_{8}=b_{1,3}$$b_{7}=b_{1,2}$$b_{6}=b_{1,1}$$b_{5}=b_{1,0}$$b_{4}=b_{0,3}$$b_{3}=b_{0,2}$
$b_{2}=b_{0,1}$$b_{1}=b_{0,0}$Interval Boundaries $b_{r}$Index $r$Exponential
functionPiecewise linear interpolations

Figure 2: Sketch of the grouping of the interval $I$ into sub-intervals.

###  4.2 Solving an MILP Formulation

Consider the resulting instance after all steps from Section 4.1 have been
applied. Nearly all previous approaches used a mix of _configuration_
variables that determine the complete schedule of a machine and _assignment_
variables that determine the position of a single job. We now combine these
different variables into a unified structure called _recursive_
configurations. The core idea of our formulation is to use an additional
_virtual_ machine $i$ of speed $b_{i}$ by placing a _corresponding_ job of
same size $b_{i}$ on a faster machine $i^{\prime}$ with
$b_{i^{\prime}}<b_{i}$, in effect simulating the virtual machine $i$ on
machine $i^{\prime}$. In other words, by placing more jobs than the problem
requires, we are also allowed to use more machines of the same size than the
problem provides. By applying this idea recursively, we can cover a large
range of job processing times with configurations of limited range only, as
the virtual machines allow us to merge several short jobs (with respect to to
a certain machine speed) into a long job. Furthermore, this approach also
allows us to successively build a configuration from other configurations,
significantly reducing the number of overall configurations necessary.

For $k=0,\ldots,\kappa$, we define the set
$G_{k}\coloneqq\\{r\in\\{1,\ldots,\tau\\}\mid
b_{r}\in[b_{k,0},b_{k,\lambda}]\\}$ of indices of affine slices in our
rounding scheme and partition it into the sets
$G_{k}^{\text{even}}\coloneqq\\{r\in G_{k}\mid r=0\bmod 2\\}$ and
$G_{k}^{\text{odd}}\coloneqq G_{k}\backslash G_{k}^{\text{even}}$. For
$i=1,\ldots,\tau$, we define the set
$H_{i}\coloneqq\\{j\in\\{1,\ldots,\tau\\}\mid b_{j}\in(\delta b_{i},b_{i}]\\}$
of indices of _long_ job speeds, which use more than $\delta b_{i}$ and less
than the entire machine speed $b_{i}$.

We will now define _configurations_. All configurations are vectors
$\bm{\gamma}$ with $\tau$ entries, each representing multiples of scaled
processing times in $\bm{b}=(b_{1},\ldots,b_{\tau})$. In the following, we
describe the configurations for machines with speed $b_{i}$.

The set $\mathcal{C}_{i}^{(1)}$ contains all the exact combinations
$b_{j}+b_{j^{\prime}}=b_{i}$ as described in Equation 3. With
$\bm{e}_{j}\in\\{0,1\\}^{\tau}$ being the $j$-th unit vector, let

$\displaystyle\mathcal{C}_{i}^{(1)}\coloneqq\\{\bm{e}_{j}+\bm{e}_{j^{\prime}}\mid
j,j^{\prime}\in G_{k(i)-1}\text{ and
}j+j^{\prime}=2\cdot(i-\lambda)\\}\enspace.$

The second set $\mathcal{C}_{i}^{(2)}$ contains the remaining feasible
configurations of long jobs, with at most one job at even and odd positions in
an affine slice $G_{k}$:

$\displaystyle\mathcal{C}_{i}^{(2)}\coloneqq\\{\bm{\gamma}\in\\{0,1\\}^{\tau}\mid{}$
$\displaystyle\bm{\gamma}\cdot\bm{b}\leq b_{i}\text{ and
}\operatorname{supp}(\bm{\gamma})\subseteq H_{i}\text{ and for all}$
$\displaystyle k=0,\ldots,\kappa-1:\sum_{r\in
G_{k}^{\text{even}}}\gamma_{r}\leq 1\text{ and }\sum_{r\in
G_{k}^{\text{odd}}}\gamma_{r}\leq 1\\}\enspace.$

Finally, the set of configurations $\mathcal{C}_{i}$ for machines with speed
$b_{i}$ is defined as
$\mathcal{C}_{i}\coloneqq\mathcal{C}_{i}^{(1)}\cup\mathcal{C}_{i}^{(2)}$. The
total number of entries in a configuration $\bm{\gamma}$ is at most
$\|\bm{\gamma}\|_{1}\leq 2\log(2\cdot 1/\delta)$. Only long jobs from $H_{i}$
are used, and for each $k$ there is at most one job at an even or odd position
in $G_{k}$, respectively. We can bound the number of configurations in
$\mathcal{C}_{i}^{(1)}$ by $\lambda^{2}$, and the number of configurations in
$\mathcal{C}_{i}^{(2)}$ by $(\lambda^{2})^{2\log(2\cdot 1/\delta)}\in
2^{\mathcal{O}(\log^{2}(1/\delta))}$, which implies $|\mathcal{C}_{i}|\in
2^{\mathcal{O}(\log^{2}(1/\delta))}$.

We require integrality in the configuration variables only for the fastest
$L\coloneqq\lambda\lceil\log(1/\delta^{3}\log(1/\delta))\rceil\in\mathcal{O}(1/\delta\log(1/\delta))$
machine speeds. Intuitively, we just need to assign configurations integrally
on these machines, as all remaining configurations are very short relative to
the machines with the fastest speed. Hence, we can assign them fractionally
and round them later on. The overhead from rounding is then scheduled on a
fastest machine.

Recall that the number of jobs with processing time $b_{j}$ in configuration
$\bm{\gamma}$ is $\gamma_{j}$, the number of machines with speed $b_{i}$ is
$\mu_{i}$, and the number of jobs with scaled processing time $b_{j}$ is
$\eta_{j}$. The resulting MILP is:

$\displaystyle\sum_{\bm{\gamma}\in\mathcal{C}_{i}}x_{i,\bm{\gamma}}-\mu_{i}$
$\displaystyle\operatorname{for}\;i=1,\ldots,\tau$ $\displaystyle
x_{i,\bm{\gamma}}$ $\displaystyle\geq 0\;$
$\displaystyle\operatorname{for}\;i=1,\ldots,\tau;\leavevmode\nobreak\
\bm{\gamma}\in\mathcal{C}_{i}$ $\displaystyle x_{i,\bm{\gamma}}$
$\displaystyle\in\mathbb{Z}_{\geq 0}\;$
$\displaystyle\operatorname{for}\;i=1,\ldots,L;\leavevmode\nobreak\
\bm{\gamma}\in\mathcal{C}_{i}.$ (recursive-MILP)

The constraints (LABEL:eq:virtual) enforce that the number of additional
virtual machines of any speed equals the number of additional corresponding
jobs of that same size scheduled somewhere else. The constraints
(LABEL:eq:pack) ensure that at least as many jobs of each size are assigned in
configurations, as are required by the problem. We show (recursive-MILP) is
feasible, up to an approximation factor, for a feasible instance.

######  Lemma 24.

If the original $Q||C_{\max}$-instance $\mathcal{I}$ has a schedule $\sigma$
with makespan $T$, then (recursive-MILP) is feasible for makespan
$(1+17\delta)\cdot T$.

For (recursive-MILP), the integer subproblem has
$m=2L\in\mathcal{O}(1/\delta\log(1/\delta))$ constraints and maximal $1$-norm
of a column $\max\|A_{i}\|_{1}\in\mathcal{O}(\log(1/\delta))$. The first $L$
machine speeds have $L\cdot
2^{\mathcal{O}(\log^{2}(1/\delta)}=2^{\mathcal{O}(\log^{2}(1/\delta))}$
configurations, i.e., integer variables. By Theorem 2 and Lemma 12, if there
is a feasible solution of (recursive-MILP), then there is also one with
$\mathcal{O}(1/\delta\log(1/\delta)\log(\log(1/\delta)))$ positive integer
variables. Lemma 13 thus implies that we can solve (recursive-MILP)($S$) in
time
$2^{\mathcal{O}(1/\delta\log^{3}(1/\delta)\log(\log(1/\delta)))}\cdot\log(N)^{\mathcal{O}(1)}$,
as the encoding size is $\langle\text{\eqref{recursive-
MILP}}(S)\rangle\leq(1/\delta\log(N))^{\mathcal{O}(1)}$. Note that this is the
dominant run time in terms of $1/\delta$. We thus either find a feasible
solution for the current makespan guess $T$, or discover that no such solution
exists. In the latter case, we discard our current makespan guess and increase
it in the next step of the binary search.

###  4.3 Constructing a Schedule

We need to construct a schedule from a solution $\bm{x}^{\star}$ to
(recursive-MILP). By constraints (LABEL:eq:pack), we know that
$\bm{x}^{\star}$ schedules each job in some configuration. By constraints
(LABEL:eq:virtual), the number of virtual machines equals the additional
number of corresponding jobs with equal size scheduled in some configuration.
Managing to assign all configurations within an approximate makespan to
machines would therefore be a valid schedule. We use the Section 4.3 for this:

AssignConfsToMachines
Input: A feasible solution $\bm{x}^{\star}$ to (recursive-MILP).
Output: An approximate schedule $\sigma$ to the pre-processed instance.
$\displaystyle\hskip 3.87498pt\text{\scriptsize 1}:\hskip 9.00002pt$
$\displaystyle\vphantom{\rule[1.93748pt]{0.0pt}{0.0pt}}\mathmakebox{}\mathbf{for}\
\text{decreasing machine speeds $b_{i}$}:$
$\displaystyle\mathmakebox{}\mathbf{for}\ \text{each
$\bm{\gamma}\in\mathcal{C}_{i}$}:$ assign $\lfloor x_{i,\bm{\gamma}}\rfloor$
copies of $\bm{\gamma}$ to machines with speed $b_{i}$
$\displaystyle\mathmakebox{}\mathbf{if}\
x_{i,\bm{\gamma}}\not\in\mathbb{Z}_{\geq 0}:\text{assign another copy of
$\bm{\gamma}$ to a fastest machine}$ $\displaystyle\mathmakebox{}\mathbf{for}\
\text{each processing time $b_{j}$ used in $\bm{\gamma}$}:$ assign as many
jobs of processing time $b_{j}$ to machines with configuration $\bm{\gamma}$
// stop when all jobs are packed or all configurations are filled
$\displaystyle\mathmakebox{}\mathbf{for}\ \text{each job in a configuration
$\bm{\gamma}$ not filled}:$ create a virtual machine with the same speed as
the corresponding job $\displaystyle\mathmakebox{}\mathbf{return}\ \text{the
resulting schedule $\sigma$}$

######  Lemma 25.

Section 4.3 gives a schedule of makespan at most $(1+5\delta)\cdot T$ from a
feasible solution $\bm{x}^{\star}$ to (recursive-MILP) in time
$2^{\mathcal{O}(1/\delta)}+\mathcal{O}(N\log^{2}(N))$.

##  5 Uniform Machine Types

It is well-known that for the very general $R||C_{\max}$ problem one cannot
obtain a $(3/2-\varepsilon)$-approximation in polynomial time for any
$\varepsilon>0$, unless $\mathsf{P}=\mathsf{NP}$ [42]. In this problem, if job
$j$ is processed on machine $i$, it takes time $p_{i,j}$. As these values do
not need to be related (in contrast to the uniform case, where
$p_{i,j}=p_{j}/s_{i}$), this problem is often called scheduling on _unrelated
machines_. To understand the approximability of this problem in more depth,
Jansen and Maack [31] studied the problem $R_{K}||C_{\max}$, where there are
$K$ _machine types_. They presented an EPTAS with run time
$2^{\mathcal{O}(K\log(K)1/\varepsilon\log^{4}(1/\varepsilon))}+\langle\mathcal{I}\rangle^{\mathcal{O}(1)}$.
They also consider the generalization $R_{K}Q||C_{\max}$, where we have $K$
machine types and for each type, the machines can have different uniform
speeds. For $R_{K}Q||C_{\max}$, they provided an EPTAS with run time
$2^{\mathcal{O}(K\log(K)1/\varepsilon^{3}\log^{5}(1/\varepsilon))}+\langle\mathcal{I}\rangle^{\mathcal{O}(1)}$.
To show the generality of our approach, we construct an EPTAS with improved
run time of
$2^{\mathcal{O}(K\log(K)1/\varepsilon\log^{3}(1/\varepsilon)\log(\log(1/\varepsilon)))}+\mathcal{O}(K\cdot
N)$. This suggests that adding uniform machines to each machine type does not
increase the complexity in approximating the generalized problem. The
exponential improvement in $\varepsilon$ is enabled by our recursive
configurations formulation. It allows us to apply our support size bound
globally to the complete MILP. In contrast, the original approach needs to
distinguish simple and complex configurations for each machine type locally.
The improvement of the polynomial dependency in $K\cdot N$ to
$\mathcal{O}(K\cdot N)$, which is linear in the input size
$\langle\mathcal{I}\rangle$, is the result of analyzing job types instead of
individual jobs.

Problem Instance Format. The input for $R_{K}Q||C_{\max}$ consists of $N$ jobs
and $M$ machines. Each job has $K$ processing times $p_{j,k}$, given as a
matrix $\mathbb{N}^{K\times N}$. Each machine has one of the $K$ types and a
speed $s_{i}$, given as $(\\{1,\ldots,K\\}\times\mathbb{N})^{M}$. We
generalize the assumption of sorted inputs from $Q||C_{\max}$ and assume that
for each machine type, we are also given lists of the jobs and machines,
sorted by their processing time and speed respectively. Such orders can be
computed in time $\mathcal{O}(K\cdot N\log(N))$, same as $Q||C_{\max}$ for
$K=1$.

###  5.1 Preprocessing

We extended our preprocessing for $Q||C_{\max}$, resulting in job counts
$\eta_{j}$, machine counts $\mu_{i,k}$ and a makespan guess $T$. Again, if
$M>N$ for any machine type, we simply discard the slowest machines, hence
$M\leq K\cdot N$. A $N$-approximation to the optimal makespan is found by
assigning each job to the machine where it has the shortest completion time.
This approach gives the upper bound $\operatorname{UB}\coloneqq
N\cdot\max_{j}\min_{k}p_{j,k}/s_{k,\max}$ (a direct generalization of $N\cdot
p_{\max}/s_{\max}$ in $Q||C_{\max}$). Any processing time $p_{j,k}$ larger
than $\operatorname{UB}\cdot s_{k,\max}$ can then be set to $\infty$. For
every machine class, a variant of Step 1 in $Q||C_{\max}$ can be performed,
that removes negligible machines and negligible jobs. More concretely, for
each machine class $k$, jobs are assigned to a fastest machine $s_{k,\max}$,
if they are smaller than $\delta\operatorname{UB}s_{k,\max}/N^{2}$, and
machines are dropped if they are slower than $\delta s_{k,\max}/N$. Hence, we
have a ratio of $p_{k,\max}/p_{k,\min}\leq N^{2}/\delta$. All of these steps
can be performed in time $\mathcal{O}(K\cdot N)$.

By repeating Step 2 for all machine types, we round all inputs in total time
$\mathcal{O}(K\cdot(N+1/\delta\log(1/\delta\cdot N)))$. Afterwards, there are
$\tilde{\tau}\coloneqq\log_{1+\delta}(1/\delta\cdot
N^{2})\in\mathcal{O}(1/\delta\log(1/\delta\cdot N))$ different job speeds left
for any machine type. Hence, there can be at most $\tilde{\tau}^{K}$ different
job types in total. We count the number of jobs of type $j$ for
$j=1,\ldots,\tau^{K}$ as $\tilde{\eta}_{j}$, in time $\mathcal{O}(K\cdot
N+\tilde{\tau}^{K})$. For all machine types $k$, the machine speed counts
$\tilde{\mu}_{i,k}$ behave as before. We perform binary search for the
makespan as in Step 3 to reduce the optimization into a feasibility problem.
For any machine type, the rounded values $b_{r}$ can be set up just as before
in Step 4. From this, we obtain the numbers of machines $\mu_{i,k}$ and jobs
$\eta_{j}$ of each type. By a similar argument, all preconditioning takes time
$\mathcal{O}(1/\delta^{6\cdot K})+\mathcal{O}(K\cdot N)$.

###  5.2 Solving an MILP Formulation

After our preconditioning, we modify the MILP used by Jansen and Maack to
accommodate our rounding scheme. Let
$\mathcal{J}_{i,k}\coloneqq\\{j\in\\{1,\ldots,{\tau^{K}}\\}\mid
b_{j_{k}}=b_{i}\\}$ be the set of indexes of jobs with rounded processing time
$b_{i}$ on machines of type $k$. Our MILP-formulation for $R_{K}Q||C_{\max}$
is:

$\displaystyle\sum_{i^{\prime}=1}^{\tau}\sum_{\bm{\gamma}\in\mathcal{C}_{i^{\prime}}}\gamma_{i}\cdot
x_{i^{\prime},\bm{\gamma},k}-\sum_{j\in\mathcal{J}_{i,k}}y_{j,k}$
$\displaystyle\geq\sum_{\bm{\gamma}\in\mathcal{C}_{i}}x_{i,\bm{\gamma},k}-\mu_{i,k}\geq
0$ $\displaystyle\operatorname{for}\;i=1,\ldots,\tau;\;k=1,\ldots,K$ (6)
$\displaystyle\sum_{k=1}^{K}y_{j,k}$ $\displaystyle\geq\eta_{j}$
$\displaystyle\operatorname{for}\;j=1,\ldots,{\tau^{K}}$ (7) $\displaystyle
x_{i,\bm{\gamma},k}$ $\displaystyle\geq 0$
$\displaystyle\operatorname{for}\;i=1,\ldots,\tau;\;\bm{\gamma}\in\mathcal{C}_{i};\;k=1,\ldots,K$
$\displaystyle x_{i,\bm{\gamma},k}$ $\displaystyle\in\mathbb{Z}_{\geq 0}$
$\displaystyle\operatorname{for}\;i=1,\ldots,L;\;\bm{\gamma}\in\mathcal{C}_{i};\;k=1,\ldots,K$
$\displaystyle y_{j,k}$ $\displaystyle\geq 0$
$\displaystyle\operatorname{for}\;j=1,\ldots,\tau;\;k=1,\ldots,K\enspace.$
(uniform-MILP)

We maintain $x$ for the configuration variables, adding an index for the
machine class. The assignment variables $y$ determine the machine class where
a job is scheduled. For the uniform part, described by the constraints (6), we
no longer directly give job amounts $\eta_{j}$, but instead determine the
_number of jobs_ assigned to a slot size. Constraints (7) ensure that all jobs
are assigned to some machine type.

Each variable $y_{j,k}$ only occurs in two constraints, with coefficients $\pm
1$, and does therefore not affect the maximal column norm $A_{\max}$.

By Lemma 12, if there is a feasible solution for the integral $x_{i,\gamma,k}$
configuration variables, then there is also one with support size
$\mathcal{O}(K\cdot 1/\delta\log(1/\delta)\log(\log(1/\delta)))$. There are
$K\cdot 2^{\mathcal{O}(\log^{2}(1/\delta))}$ integral configuration variables
in total. Using Lemma 13, we find a feasible solution to (uniform-MILP) in
time

$\displaystyle 2^{\mathcal{O}(K\log(K)\cdot
1/\delta\log^{3}(1/\delta)\log(\log(1/\delta)))}+\mathcal{O}(K\cdot
N)\enspace.$

###  5.3 Constructing a Schedule

Now, we have a feasible solution $(\bm{\hat{x}},\bm{\hat{y}})$ to (uniform-
MILP), from which we need to construct a schedule. Fixing some solution
$\bm{\hat{x}}$ leaves only the assignment variables in the following linear
program with constraint matrix $A_{x}$:

$\displaystyle-\sum_{j\in\mathcal{J}_{i,k}}y_{j,k}\geq
c_{i,k}(\bm{\hat{x}})\quad\text{and}\quad\sum_{k=1}^{K}y_{j,k}\geq\eta_{j}\qquad
y_{j,k}\geq 0\enspace.$ (R-uniform-LP($\bm{\hat{x}}$))

As shown by Hoffman and Gale [24], any matrix, where each column vector has at
most the $2$ non-zero opposite sign entries $1$ and $-1$, is totally
unimodular. This is the case for the constraint matrix $A_{x}$ of (R-uniform-
LP($\bm{\hat{x}}$)), as each variable occurs at most once with coefficient
$-1$ in constraints (6) and once with coefficient $1$ in constraints (7).
Hence, $A_{x}$ is totally unimodular and any vertex solution is already
integral. For any machine type $k$, we therefore have an integral number of
jobs of each size assigned to it and a compatible feasible solution
$\bm{\hat{x}_{k}}$. Using the techniques of LABEL:sec:fasterSched, we can
construct a schedule $\sigma_{k}$ for each machine type in time
$2^{\mathcal{O}(1/\delta\log^{2}(1/\delta))}+\mathcal{O}(N)$. Together, these
give a complete schedule $\sigma\coloneqq\bigcup_{k}\sigma_{k}$ in time
$2^{K\cdot 1/\delta\log^{2}(1/\delta))}+\mathcal{O}(K\cdot N)$, thus proving
the following theorem. See 9

## References

  * Aliev et al. [2017] I. Aliev, J. A. De Loera, T. Oertel, and C. O’Neill.  Sparse solutions of linear Diophantine equations.  _SIAM J. Appl. Algebra Geom._ , 1(1):239–253, 2017.  doi: 10.1137/16M1083876.
  * Aliev et al. [2018] I. Aliev, J. A. De Loera, F. Eisenbrand, T. Oertel, and R. Weismantel.  The support of integer optimal solutions.  _SIAM J. Optim._ , 28(3):2152–2157, 2018.  doi: 10.1137/17M1162792.
  * Aliev et al. [2022] I. Aliev, G. Averkov, J. A. De Loera, and T. Oertel.  Sparse representation of vectors in lattices and semigroups.  _Math. Program._ , 192(1-2, Ser. B):519–546, 2022\.  doi: 10.1007/s10107-021-01657-8.
  * Azar and Epstein [1998] Y. Azar and L. Epstein.  Approximation schemes for covering and scheduling in related machines.  In _Proc. APPROX 1998_ , volume 1444 of _Lecture Notes Comput. Sci._ , pages 39–47. 1998.  doi: 10.1007/BFb0053962.
  * Bansal et al. [2016] N. Bansal, T. Oosterwijk, T. Vredeveld, and R. van der Zwaan.  Approximating vector scheduling: almost matching upper and lower bounds.  _Algorithmica_ , 76(4):1077–1096, 2016.  doi: 10.1007/s00453-016-0116-0.
  * Bauer [1960] H. Bauer.  Minimalstellen von Funktionen und Extremalpunkte. II.  _Arch. Math._ , 11:200–205, 1960.  doi: 10.1007/BF01236933.
  * Berndt et al. [2021] S. Berndt, K. Jansen, and K.-M. Klein.  New bounds for the vertices of the integer hull.  In _Proc. SODA 2021_ , pages 25–36. 2021.  doi: 10.1137/1.9781611976496.3.
  * Berndt et al. [2022] S. Berndt, M. A. Deppert, K. Jansen, and L. Rohwedder.  Load balancing: The long road from theory to practice.  In _Proc. ALENEX 2022_ , pages 104–116, 2022.  doi: 10.1137/1.9781611977042.9.
  * Brauner et al. [2005] N. Brauner, Y. Crama, A. Grigoriev, and J. van de Klundert.  A framework for the complexity of high-multiplicity scheduling problems.  _J. Comb. Optim._ , 9(3):313–323, 2005.  doi: 10.1007/s10878-005-1414-7.
  * Brinkop and Jansen [2022] H. Brinkop and K. Jansen.  High multiplicity scheduling on uniform machines in FPT-Time.  Technical report, 2022.  https://arxiv.org/abs/2203.01741.
  * Browne et al. [2021] P. Browne, R. Egan, F. Hegarty, and P. Ó Catháin.  A survey of the Hadamard maximal determinant problem.  _Electron. J. Combin._ , 28(4):Paper No. 4.41,35, 2021.  doi: 10.37236/10367.
  * Chatzigeorgiou [2013] I. Chatzigeorgiou.  Bounds on the Lambert function and their application to the outage analysis of user cooperation.  _IEEE Comm. Lett._ , 17(8):1505–1508, 2013.  doi: 10.1109/LCOMM.2013.070113.130972.
  * Chen et al. [2018] L. Chen, K. Jansen, and G. Zhang.  On the optimality of exact and approximation algorithms for scheduling problems.  _J. Comput. Syst. Sci._ , 96:1–32, 2018.  doi: 10.1016/j.jcss.2018.03.005.
  * Cho and Sahni [1980] Y. Cho and S. Sahni.  Bounds for list schedules on uniform processors.  _SIAM J. Comput._ , 9(1):91–103, 1980.  doi: 10.1137/0209007.
  * Eisenbrand and Shmonin [2006] F. Eisenbrand and G. Shmonin.  Carathéodory bounds for integer cones.  _Oper. Res. Lett._ , 34(5):564–568, 2006.  doi: 10.1016/j.orl.2005.09.008.
  * Filippi and Romanin-Jacur [2009] C. Filippi and G. Romanin-Jacur.  Exact and approximate algorithms for high-multiplicity parallel machine scheduling.  _J. Sched._ , 12(5):529–541, 2009.  doi: 10.1007/s10951-009-0122-z.
  * Goemans and Rothvoss [2020] M. X. Goemans and T. Rothvoss.  Polynomiality for bin packing with a constant number of item types.  _J. ACM_ , 67(6), 2020.  doi: 10.1145/3421750.
  * Gonzalez et al. [1977] T. Gonzalez, O. H. Ibarra, and S. Sahni.  Bounds for LPT schedules on uniform processors.  _SIAM J. Comput._ , 6(1):155–166, 1977.  doi: 10.1137/0206013.
  * Graham et al. [1979] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan.  Optimization and approximation in deterministic sequencing and scheduling: a survey.  volume 5, pages 287–326. 1979.  doi: 10.1016/S0167-5060(08)70356-X.  Discrete optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), II.
  * Granot and Skorin-Kapov [1993] F. Granot and J. Skorin-Kapov.  On polynomial solvability of the high multiplicity total weighted tardiness problem.  _Discrete Appl. Math._ , 41(2):139–146, 1993\.  doi: 10.1016/0166-218X(93)90034-L.
  * Grötschel et al. [1988] M. Grötschel, L. Lovász, and A. Schrijver.  _Geometric algorithms and combinatorial optimization_ , volume 2 of _Algorithms and Combinatorics: Study and Research Texts_.  1988\.  ISBN 3-540-13624-X.  doi: 10.1007/978-3-642-97881-4.
  * Haase and Zetzsche [2019] C. Haase and G. Zetzsche.  Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests.  In _Proc. LICS 2019_ , page [14 pp.]. IEEE, [Piscataway], NJ, 2019\.  doi: 10.1109/LICS.2019.8785850.
  * Hamada [2010] T. Hamada.  A Bayesian sequential single machine batching and scheduling problem with random setup time.  _J. Oper. Res. Soc. Japan_ , 53(1):79–100, 2010\.  doi: 10.15807/jorsj.53.79.
  * Heller and Tompkins [1956] I. Heller and C. B. Tompkins.  _An extension of a theorem of Dantzig’s_ , pages 247–254.  Annals of Mathematics Studies, no. 38. 1956.  doi: 10.1515/9781400881987-015.
  * Hochbaum and Shamir [1991] D. S. Hochbaum and R. Shamir.  Strongly polynomial algorithms for the high multiplicity scheduling problem.  _Oper. Res._ , 39(4):648–653, 1991.  doi: 10.1287/opre.39.4.648.
  * Hochbaum and Shanthikumar [1990] D. S. Hochbaum and J. G. Shanthikumar.  Convex separable optimization is not much harder than linear optimization.  _J. Assoc. Comput. Mach._ , 37(4):843–862, 1990\.  doi: 10.1145/96559.96597.
  * Hochbaum and Shmoys [1988] 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.  doi: 10.1137/0217033.
  * Hochbaum et al. [1992] D. S. Hochbaum, R. Shamir, and J. G. Shanthikumar.  A polynomial algorithm for an integer quadratic nonseparable transportation problem.  _Math. Programming_ , 55(3, Ser. A):359–371, 1992\.  doi: 10.1007/BF01581207.
  * Jansen [2010] K. Jansen.  An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables.  _SIAM J. Discrete Math._ , 24(2):457–485, 2010\.  doi: 10.1137/090749451.
  * Jansen [2012] K. Jansen.  A fast approximation scheme for the multiple knapsack problem.  In _Proc. SOFSEM 2012_ , volume 7147 of _Lecture Notes Comput. Sci._ , pages 313–324, 2012.  doi: 10.1007/978-3-642-27660-6“˙ 26.
  * Jansen and Maack [2019] K. Jansen and M. Maack.  An EPTAS for scheduling on unrelated machines of few different types.  _Algorithmica_ , 81(10):4134–4164, 2019.  doi: 10.1007/s00453-019-00581-w.
  * Jansen and Robenek [2012] K. Jansen and C. Robenek.  Scheduling jobs on identical and uniform processors revisited.  In _Proc. WAOA 2011_ , volume 7164 of _Lecture Notes Comput. Sci._ , pages 109–122, 2012.  doi: 10.1007/978-3-642-29116-6“˙ 10.
  * Jansen and Rohwedder [2019] K. Jansen and L. Rohwedder.  On integer programming and convolution.  In _Proc. ITCS 2019_ , volume 124 of _Leibniz Int. Proc. Inform._ , pages Art. No. 43,17, 2019.  doi: 10.4230/LIPIcs.ITCS.2019.43.
  * Jansen and Rohwedder [2022] K. Jansen and L. Rohwedder.  On integer programming, discrepancy, and convolution.  _Math. Oper. Res._ , 2022.  doi: 10.1287/moor.2022.1308.
  * Jansen et al. [2016] K. Jansen, K.-M. Klein, and J. Verschae.  Closing the gap for makespan scheduling via sparsification techniques.  In _Proc. ICALP 2016_ , volume 55 of _Leibniz Int. Proc. Informatics_ , pages Art. No. 72,13, 2016.  doi: 10.4230/LIPIcs.ICALP.2016.72.
  * Jansen et al. [2020] K. Jansen, K.-M. Klein, and J. Verschae.  Closing the gap for makespan scheduling via sparsification techniques.  _Math. Oper. Res._ , 45(4):1371–1392, 2020.  doi: 10.1287/moor.2019.1036.
  * Kannan [1987] R. Kannan.  Minkowski’s convex body theorem and integer programming.  _Math. Oper. Res._ , 12(3):415–440, 1987.  doi: 10.1287/moor.12.3.415.
  * Knop et al. [2019] D. Knop, M. Koutecký, A. Levin, M. Mnich, and S. Onn.  Multitype integer monoid optimization and applications.  _CoRR_ , abs/1909.07326, 2019.  doi: 10.48550/arXiv.1909.07326.
  * Koutecký and Zink [2020] M. Koutecký and J. Zink.  Complexity of scheduling few types of jobs on related and unrelated machines.  In _Proc. ISAAC 2020_ , volume 181 of _Leibniz Int. Proc. Inform._ , pages Art. No. 18,17, 2020.  doi: 10.4230/LIPIcs.ISAAC.2020.18.
  * Kuncak and Rinard [2007] V. Kuncak and M. Rinard.  Towards efficient satisfiability checking for Boolean algebra with Presburger arithmetic.  In _Automated deduction—CADE-21_ , volume 4603 of _Lecture Notes Comput. Sci._ , pages 215–230, 2007.  doi: 10.1007/978-3-540-73595-3“˙ 15.
  * Lenstra [1983] H. W. Lenstra, Jr.  Integer programming with a fixed number of variables.  _Math. Oper. Res._ , 8(4):538–548, 1983.  doi: 10.1287/moor.8.4.538.
  * Lenstra et al. [1990] J. K. Lenstra, D. B. Shmoys, and É. Tardos.  Approximation algorithms for scheduling unrelated parallel machines.  _Math. Programming_ , 46(3, (Ser. A)):259–271, 1990.  doi: 10.1007/BF01585745.
  * Manurangsi and Raghavendra [2017] P. Manurangsi and P. Raghavendra.  A birthday repetition theorem and complexity of approximating dense CSPs.  In _Proc. ICALP 2017_ , volume 80 of _Leibniz Int. Proc. Inform._ , pages Art. No. 78,15. 2017.  doi: 10.4230/LIPIcs.ICALP.2017.78.
  * McCormick et al. [2001] S. T. McCormick, S. R. Smallwood, and F. C. R. Spieksma.  A polynomial algorithm for multiprocessor scheduling with two job lengths.  _Math. Oper. Res._ , 26(1):31–49, 2001.  doi: 10.1287/moor.26.1.31.10590.
  * Oertel et al. [2019] T. Oertel, J. Paat, and R. Weismantel.  Sparsity of integer solutions in the average case.  In _Proc. IPCO 2019_ , volume 11480 of _Lecture Notes Comput. Sci._ , pages 341–353. 2019.  doi: 10.1007/978-3-030-17953-3˙26.
  * Pratt-Hartmann [2008] I. Pratt-Hartmann.  On the computational complexity of the numerically definite syllogistic and related logics.  _Bull. Symbolic Logic_ , 14(1):1–28, 2008.  doi: 10.2178/bsl/1208358842.
  * Psaraftis [1980] H. N. Psaraftis.  A dynamic programming approach for sequencing groups of identical jobs.  _Oper. Res._ , 28(6):1347–1359, 1980.  doi: 10.1287/opre.28.6.1347.
  * Rohwedder [2019] L. Rohwedder.  _Algorithms for Integer Programming and Allocation_.  phdthesis, 2019.  URL https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/dissertation_derivate_00008487/Lars-Rohwedder.pdf.
  * Rothvoss [2016] T. Rothvoss.  Integer optimization and lattices, 2016.  URL https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf.  Lecture Notes.
  * Stanley [2012] R. P. Stanley.  _Enumerative combinatorics. Volume 1_ , volume 49 of _Cambridge Studies in Advanced Mathematics_.  Second edition, 2012.  ISBN 978-1-107-60262-5.  doi: 10.1017/CBO9781139058520.
  * Woeginger [2000] G. J. Woeginger.  A comment on scheduling on uniform machines under chain-type precedence constraints.  _Oper. Res. Lett._ , 26(3):107–109, 2000.  doi: 10.1016/S0167-6377(99)00076-0.