n}})}$. Furthermore, $\omega=O(\gamma)=O(\frac{\log n}{\log\log n})$. Thus,
all properties of Lemma 7 are satisfied. ∎

##  Appendix A Omitted Proofs in Section 2 \- Algorithms AL1, AL2, AL3

###  A.1 Algorithm 1

######  Lemma 12.

Consider an instance after the preprocessing of Lemma 1. For any $\epsilon>0$,
there exists an algorithm AL${}_{\ref{alg:1}}$ that returns an
$(1+O(\epsilon))$-approximate solution for $P||\sum_{i}C_{i}^{q}$ and runs in
time $(m/\epsilon)^{O(m)}$.

The algorithm can be formulated as a dynamic program. For each
$h\in\mathbb{Z}_{n}$, we create a set of states $\mathcal{F}_{h}$. A state
$(h,L_{1},\dots,L_{m})$ belongs to $\mathcal{F}_{h}$ if it is possible to
assign jobs $1,\dots,h$ on machines such that the total load on machine $i$
equals $L_{i}$ for all $i\in\mathbb{Z}_{m}$. Starting from
$(0,\dots,0)\in\mathcal{F}_{0}$, every state in $\mathcal{F}_{i-1}$ can give
rise to some states in $\mathcal{F}_{i}$ by trying all the possible assignment
of job $h$. And the solution is given by the state in $\mathcal{F}_{n}$ with
the minimum objective i.e., $\sum_{i=1}^{m}L_{i}^{q}$. Due to Lemma 1, we know
that one of the optimal solutions has a load vector
$({L_{1}^{*}},\dots,{L_{m}^{*}})\in\mathcal{F}_{n}$ satisfying $L_{i}^{*}\leq
2$ for all $i$. Clearly, the running time of Algorithm 1 is
$O(m\sum_{i}|\mathcal{F}_{i}|)$. However, the total number of states stored
during the dynamic programming can be pseudo-polynomial. Fortunately, using
the framework by Woeginger [41], we are able to trim the state space to make
it polynomial. More precisely, for any $\delta>0$ construct
$\hat{\mathcal{F}}_{1},\dots,\hat{\mathcal{F}}_{n}$ satisfying the following
property:

  * •

the size of each $\hat{\mathcal{F}}_{i}$ is bounded by $(1/\delta)^{O(m)}$;

  * •

for each $(i,L_{1},\dots,L_{m})\in\mathcal{F}_{i}$, there exists
$(i,\hat{L}_{1},\dots,\hat{L}_{m})\in\hat{\mathcal{F}}_{i}$ such that
$L_{j}\leq\hat{L}_{j}\leq L_{j}(1+\delta)^{i}$.

In Algorithm 1, we set the parameter $\delta=\epsilon/n$. Due to Lemma 1,
$n\in O(m/\epsilon)$, the total running time is bounded by
$(m/\epsilon)^{O(m)}$. Let $(n,\hat{L}_{1},\dots,\hat{L}_{m})$ be the state
with the minimum objective in $\hat{\mathcal{F}}_{n}$, and
$(n,L_{1}^{*},\dots,L_{m}^{*})$ be the state with the minimum objective in
$\mathcal{F}_{n}$. Hence, $(n,\hat{L}_{1},\dots,\hat{L}_{m})$ is an
$(1+O(\epsilon))$-approximate solution, as,

$\sum_{i}\hat{L}_{i}^{q}\leq(1+\delta)^{nq}\sum_{i}{L_{i}^{*}}^{q}\leq(1+2q\epsilon)OPT,$

where $q$ is a fixed constant.

Algorithm 1 Pseudo Code Description of AL1

Input: $I,\epsilon$
Output:
$\min\\{\sum_{i=1}^{m}\hat{L}_{i}^{q}:(\hat{L}_{1},\dots,\hat{L}_{m})\in\hat{\mathcal{F}_{n}}\\}$

1: $\delta=\epsilon/n$

2:
$\Gamma=\\{[0],[\epsilon,\epsilon(1+\delta)),[\epsilon(1+\delta),\epsilon(1+\delta)^{2}),\dots\\}$

3: $\hat{\mathcal{F}}_{0}=\\{(0,\dots,0)\\}$

4: for $j=1$ to $n$ do

5: $\mathcal{F}^{\prime}_{j}=\emptyset$

6: for all $(L_{1},\dots,L_{m})\in\mathcal{F}_{i-1}$ do

7: for all $i\in[1,m]$ and $L_{i}+p_{j}\leq 2$ do

8:
$\mathcal{F}^{\prime}_{j}=\mathcal{F}^{\prime}_{j}\cup(L_{1},\dots,L_{i-1},L_{i}+p_{j},L_{i+1},\dots,L_{m})$

9: end for

10: end for

11: $\hat{\mathcal{F}}_{j}=\emptyset$

12: for all $S\in\Gamma^{m}$ do

13: for $i=1$ to $m$ do

14: $\hat{L}_{i}=\max\\{L_{i}:(\dots,L_{i},\dots)\in\mathcal{F}^{\prime}\cap
S\\}$

15: end for

16:
$\hat{\mathcal{F}}_{j}=\hat{\mathcal{F}}_{j}\cup(\hat{L}_{1},\dots,\hat{L}_{m})$

17: end for

18: end for

###  A.2 Algorithm 2

We first recall Lemma 2 and then present its proof.

######  Lemma 2.

Consider an instance after the preprocessing of Lemma 1. For any $\epsilon>0$,
there exists an algorithm AL2 that outputs an $(1+O(\epsilon))$-approximation
solution for $P||\sum_{i}C_{i}^{q}$ within $m^{\tilde{O}(1/\sqrt{\epsilon})}$
time.

###### Proof.

Based on Lemma 3, we design AL2 as a dynamic program as follows.

We say that a vector $(i,v,u_{1},u_{2},\ldots,u_{\tau})$ is a valid state if
it is possible to assign the $u_{h}$ largest jobs in $\mathcal{G}_{h}$, for
each $h$, on the first $i$ machines with the objective equal to $v$. In our
algorithm, for each $i\in\\{0,\ldots,m\\}$, we construct a set
$\mathcal{F}_{i}$ of valid states. Start from $(0,\dots,0)\in\mathcal{F}_{0}$.
To construct the valid states in $\mathcal{F}_{i}$, we consider a state in
$\mathcal{F}_{i-1}$ and try all possible assignments of jobs to machine $i$
that respect the ordering of jobs given by Lemma 3 and the load bound for each
machine implied by Lemma 1. Given the sets
$\mathcal{F}_{0},\ldots,\mathcal{F}_{m}$, the answer can be found by searching
the state with the minimum objective in $\mathcal{F}_{m}$. In order to limit
the number of states, we can eliminate _dominated_ states. Namely, if two
states $(i,v,u_{1},\dots,u_{\tau})$ and $(i,v^{\prime},u_{1},\dots,u_{\tau})$
in $\mathcal{F}_{i}$ satisfy $v^{\prime}<v$, then we say that
$(i,v^{\prime},u_{1},\dots,u_{\tau})$ is dominated and delete it from
$\mathcal{F}_{i}$.

The overall running time of AL2 can be bounded as follows. Recall that by
Lemma 1, $p_{j}\geq\epsilon$ and that the load of each machine is at most 2.
Hence, each state in $\mathcal{F}_{i-1}$ can give rise to at most
$(2/\epsilon+1)^{\tau}$ (dominated or undominated) states in
$\mathcal{F}_{i}$. As also the number of jobs in each set $\mathcal{G}_{h}$ is
bounded by $2m/\epsilon$, the number of undominated states in
$\mathcal{F}_{i}$ is at most
$(2m/\epsilon+1)^{\tau}=m^{\tilde{O}(\sqrt{1/\epsilon})}$. Hence, each set
$\mathcal{F}_{i}$ can be constructed in time
$(2/\epsilon+1)^{\tau}m^{\tilde{O}(\sqrt{1/\epsilon})}=m^{\tilde{O}(\sqrt{1/\epsilon})}$,
which implies the same bound for the overall running of our dynamic
programming algorithm. The lemma follows. ∎

###  A.3 Algorithm 3

The goal of this subsection is to prove the following lemma.

######  Lemma 13.

Consider an instance after the preprocessing of Lemma 1. For any $\epsilon>0$,
there exists an algorithm that outputs a feasible schedule for well structured
instance of $P||\sum_{i}C_{i}^{q}$ whose objective value is at most
$OPT+O(\log^{2}m)$ within $(1/\epsilon)^{O(1)}+n^{O(1)}$ time.

Recall Lemma 1, and that an approximation scheme for well structured instances
also implies an approximation scheme for general instances. Given Lemma 13 and
the fact that $OPT\geq m$ for well structured instances, we know that the
additive error $O(\log^{2}m)\leq\epsilon OPT$ if
$m=\Omega(1/\epsilon\log^{2}(1/\epsilon))$. Hence, Theorem 1 is proved.

In the following, we present Algorithm 3, which is the algorithm claimed in
Lemma 13. Algorithm 3 modifies upon the famous algorithm for bin packing by
Karmarkar and Karp [23]. Given an instance $I$, $m(I)$ denotes the number of
machines, and $\text{size}(I)$ denotes the total processing time of jobs. To
exclude the trivial cases, if $I$ consists of less than $m(I)$ jobs, then it
is obvious that the optimal solution assigns each job to a separate machine.
Hence, in the following parts, we can assume without of loss generality there
are more than $m(I)$ jobs.

We give a very high-level description. The scheduling problem can be
interpreted as a bin packing problem where the bin number is a constraint, and
the objective is to minimize the cost of bins instead of minimizing the number
of bins (where the cost of a bin is its load to the power of $q$). Under such
an interpretation, we are able to iteratively apply the harmonic grouping
scheme to round job processing times and establish a configuration LP for the
rounded instance. Based on the extreme point solution of the configuration LP,
we assign jobs to roughly $m(I)/2$ machines and continue with the remaining
jobs and machines.

As discussed in Lemma 1, here we assume the processing time of all jobs in $I$
are within $[\epsilon,1]$. Suppose there are $\chi$ distinct job processing
times with $b_{1}$ jobs of processing time $p_{1}$, $b_{2}$ jobs of processing
time $b_{2}$, … , $b_{\chi}$ jobs of processing time $p_{\chi}$. Consider the
the subset of jobs that can be scheduled on a single machine, which can be
characterized by a $\chi$-tuple ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}=(t_{1j},t_{2j},\cdots,t_{\chi j})$ where $t_{ij}$ indicates the
number of jobs of processing time $p_{i}$ on this machine. We call any
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ with $t_{ij}\leq b_{i}$
for every $i$ as a configuration. Let $N$ denote the number of configurations,
let ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{1},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{2},\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{N}$ be a complete
enumeration of them.

We establish a configuration integer program for instance $I$ as follows. We
introduce a variable $x_{j}$ for each configuration
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ which indicates the
number of machines which is scheduled according to
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$. Consequently, all
machines of configuration ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ accommodate
$t_{ij}x_{j}$ jobs of processing time $p_{i}$. We define the load, or total
processing time of configuration
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ as
$L({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j})=\sum_{i=1}^{\chi}t_{ij}p_{i}$. We define the cost of configuration
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ as
$v_{j}=(\sum_{i=1}^{\chi}t_{ij}p_{i})^{q}$.

$\displaystyle\text{Conf-IP($I$)}:$ $\displaystyle\min$
$\displaystyle\sum_{j=1}^{N}{v}_{j}x_{j}$ $\displaystyle s.t.$
$\displaystyle\sum_{j=1}^{N}x_{j}=m(I)$
$\displaystyle\sum_{j=1}^{N}t_{ij}x_{j}\geq b_{i},\quad i=1,2,\cdots,\chi$
$\displaystyle x_{j}\in\mathbb{N},\quad j=1,2,\cdots,N$

Let ${OPT}_{IP}(I)$ be the optimal objective value of Conf-IP($I$). Relaxing
the integral constraint $x_{j}\in\mathbb{N}$ to $x_{j}\geq 0$ in Conf-
LP(${I}$), we obtain a configuration linear programming Conf-LP(${I}$). Let
$OPT_{LP}({I})$ be its optimal objective value, it is obvious that
$OPT_{LP}({I})\leq OPT_{IP}({I})$. We have the following lemma.

######  Lemma 14.

There exists an algorithm of running time polynomial in
$\chi,\log(m/\epsilon)$ and $1/\varsigma$, and returns a feasible extreme
point solution of objective value at most $OPT_{LP}({I})+\varsigma$ for Conf-
LP(${I}$).

###### Proof.

We consider the dual of Conf-LP(${I}$):

$\displaystyle\text{Dual-LP(${I}$)}:$ $\displaystyle\max$
$\displaystyle\sum_{i=1}^{\chi}b_{i}y_{i}-m(I)z$ $\displaystyle s.t.$
$\displaystyle\sum_{i=1}^{\chi}t_{ij}y_{i}-z\leq{v}_{j},\quad j=1,2,\cdots,N$
$\displaystyle y_{i}\geq 0,\quad j=1,2,\cdots,N$

We use a similar algorithm as that for the classical bin packing problem. We
employ the ellipsoid method to solve Dual-LP($\bar{I}$). We give a brief
description. The ellipsoid method iteratively computes a sequence of
ellipsoids $E_{0},E_{1},\cdots,$. In each iteration, it implements a
separation oracle to check whether the center of the current ellipsoid
$E_{k}$, say, $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k},z^{k})=(y_{1}^{k},\cdots,y_{\chi}^{k},z^{k})$, is feasible. If it
is, then it outputs a cut ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}-m(I)z\geq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k}-m(I)z^{k}$ where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}=(b_{1},\cdots,b_{\chi})$;
Otherwise, it finds out a violating constraint, say,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}-z\leq\bar{v}_{j}$, and
outputs ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}-z\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k}-z^{k}$. Incorporating the
cut output by the separation oracle, the ellipsoid method computes a new
ellipsoid $E_{k+1}$ and guarantees that the volume of the new ellipsoid is
smaller than $E_{k}$ by a factor of $e^{-\frac{1}{5(\chi+1)}}$. After a
polynomial number of iterations (specifically, which is polynomial in $\log
1/\varsigma$), the ellipsoid method finds a near-optimal feasible solution
with an additive error of $\varsigma$.

In their seminal work, Karmarkar and Karp [23] further prove that to compute
an approximate solution to Conf-LP(${I}$) up to an additive precision of
$\varsigma$, it suffices to construct an approximate separation oracle such
that in each iteration, instead of checking whether the center
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k},z^{k})$ is feasible and
returns a violating constraint if it is infeasible, the approximate separation
oracle checks a point $(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},\tilde{z}^{k})$ and does
the following:

  * •

If $(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},\tilde{z}^{k})$ violates
a constraint, say, ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}-\tilde{z}^{k}>{v}_{j}$,
then outputs cut ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}-{z}\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k}-\tilde{z}^{k}$;

  * •

If $(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},\tilde{z}^{k})$ does not
violate any constraint, then outputs
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}}-m(I)z\geq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}-m(I)\tilde{z}^{k}$.

Karmarkar and Karp showed that ellipsoid method equipped with the approximate
separation oracle can return a near-optimal solution within an additive error
of $O(\varsigma)$ as long as the point
$(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},\tilde{z}^{k})$ in each
iteration satisfies that

  * •

For any constraint, if ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}-\tilde{z}^{k}>{v}_{j}$,
then ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\cdot{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}-{z}^{k}>{v}_{j}$;

  * •

For the objective function, ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k}-m(I)z^{k}\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}}^{k}-m(I)\tilde{z}^{k}+\varsigma$.

Here the first property ensures that if
$(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},\tilde{z}^{k})$ is
infeasible, then $({{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},{z}^{k})$ is also
infeasible by violating the same constraint, and therefore the approximate
separation oracle proceeds exactly the same as an (accurate) separation
oracle. The second property ensures that the approximate separation oracle
will never cut off a feasible point whose objective value is significantly
better than $(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k},\tilde{z}^{k})$ by
$\varsigma$, and hence ensures the near-optimality.

Now we describe our approximate separation oracle as follows. We first round
$v_{j}$ up to be the nearest value of the form $(1+\epsilon)^{k}$ and let it
be $\bar{v}_{j}$. Notice that there are a polynomial number of distinct
rounded values. Given an arbitrary point
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k},z^{k})$, we consider all
inequalities of the form

${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k}\leq\bar{v}_{j}+z^{k}.$

Our goal is to find out a violating constraint or determine there is none.
Since there are only a polynomial number of different values for
$\bar{v}_{j}$’s, we can sequentially check for every value $(1+\epsilon)^{h}$,
whether $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k},z^{k})$ violates the
constraint ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k}\leq(1+\epsilon)^{h}+z^{k}$ for all configurations
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ such that
$(1+\epsilon)^{h-1}<({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}})^{q}\leq(1+\epsilon)^{h}$
where ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}}=(p_{1},\cdots,p_{\chi})$. We
argue that we can drop the lower bound by sequentially checking for every
value $(1+\epsilon)^{h}$, whether
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k},z^{k})$ violates the
constraint ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k}\leq(1+\epsilon)^{h}+z^{k}$ for all configurations
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ such that
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}})^{q}\leq(1+\epsilon)^{h}$.
This is because that if $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k},z^{k})$ violates
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k}\leq(1+\epsilon)^{h}+z^{k}$ but
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}})^{q}\leq(1+\epsilon)^{h-1}$,
say, $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}})^{q}$ rounded up to
$(1+\epsilon)^{h^{\prime}}$ for $h^{\prime}<h$, then
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k},z^{k})$ also violates
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k}\leq(1+\epsilon)^{h^{\prime}}+z^{k}$, which will be found out
already. Hence, finding a violating constraint is equivalent as finding a
vector ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}$ such that
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}})^{q}\leq(1+\epsilon)^{h}$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k}$ is maximized, and
comparing this maximal value with $z^{k}+(1+\epsilon)^{k}$. This is a knapsack
problem which admits a fully polynomial time approximation scheme (FPTAS).
More precisely, using the same method as Karmarkar and Karp [23], we can round
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{k}$ to some value
$\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}$ close enough such that

  * •

For any $\chi$-dimensional vector $\textstyle\bf d$ whose coordinates are non-
negative and $\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
d$}}{\mbox{\boldmath$\textstyle\bf d$}}{\mbox{\boldmath$\scriptstyle\bf
d$}}{\mbox{\boldmath$\scriptscriptstyle\bf d$}}}\|_{1}\leq n$,
$0\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
d$}}{\mbox{\boldmath$\textstyle\bf d$}}{\mbox{\boldmath$\scriptstyle\bf
d$}}{\mbox{\boldmath$\scriptscriptstyle\bf
d$}}}\cdot{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}}^{k}-{\mathchoice{\mbox{\boldmath$\displaystyle\bf
d$}}{\mbox{\boldmath$\textstyle\bf d$}}{\mbox{\boldmath$\scriptstyle\bf
d$}}{\mbox{\boldmath$\scriptscriptstyle\bf
d$}}}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}\leq\varsigma$;

  * •

In polynomial time (specifically, polynomial in $1/\varsigma$), we are able to
find ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}^{*}$ such that by taking
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}^{*}$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}$ is maximized subject to
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
p$}}{\mbox{\boldmath$\textstyle\bf p$}}{\mbox{\boldmath$\scriptstyle\bf
p$}}{\mbox{\boldmath$\scriptscriptstyle\bf p$}}})^{q}\leq(1+\epsilon)^{h}$.

Overall, our above argument ensures that in polynomial time we either
determine some configuration ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf t$}}}_{j}$ such that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}}^{k}>\bar{v}_{j}+z^{k}$ for
some $j$, and hence

${\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}}^{k}+z^{k}\geq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
t$}}{\mbox{\boldmath$\textstyle\bf t$}}{\mbox{\boldmath$\scriptstyle\bf
t$}}{\mbox{\boldmath$\scriptscriptstyle\bf
t$}}}_{j}\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}}^{k}\bar{v}_{j}+z^{k}>\bar{v}_{j}+z^{k}\geq v_{j}+z^{k};$

or we conclude there is no such configuration and guarantee that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{k}-m(I)z^{k}\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}\cdot\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}}^{k}-m(I)\tilde{z}^{k}+\varsigma$.

Hence, there exists an approximate separation oracle for Dual-LP($I$),
indicating that Dual-LP($I$) can be solved using the ellipsoid method in
polynomial time (up to arbitrary precision). Notice that the derived solution
may not necessarily be an extreme point, however, by using exactly the same
argument as that of Karmarkar and Karp [23], we can make it into an extreme
point solution. ∎

Consider the near-optimal extreme point solution
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)$ given by Lemma 14. We
denote by $\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)\rfloor=(\lfloor
x_{1}(I)\rfloor,\cdots,\lfloor x_{N}(I)\rfloor)$ the rounded solution. Similar
as the algorithm for bin packing, we assign jobs to machine according to
$\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)\rfloor$ and then proceed
with the residue instance
$I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$. Denote by
$I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$ the residue instance where
we take away jobs scheduled according to
$\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)\rfloor$ from the original
instance $I$, i.e., $I_{res}$ consists jobs in
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}(I)-\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)\rfloor$. It is easy to see
$I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$ consists of
$m(I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}))=m(I)-\sum_{j}\lfloor
x_{j}(I)\rfloor$ machines.

######  Lemma 15.

$OPT_{LP}(I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}))+OPT_{LP}(I\setminus
I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}))\leq OPT_{LP}(I)$

###### Proof.

We know each configuration of instance $I$ is also a configuration of instance
$I_{res}$ and $I\setminus
I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$. Hence, for any solution
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)$ of instance $I$,
$\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)\rfloor$ is an feasible
solution of $I\setminus I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}(I)-\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)\rfloor$ is an feasible
solution of $I_{res}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$. ∎

Similar to the bin packing algorithm by Karmarkar and Karp [23], we will
employ the harmonic grouping scheme to round the instance and apply Lemma 14
on the rounded instance. It has to be noticed that the processing time of
every job in the instance is no more than 1 which is guaranteed by Lemma 1.
The harmonic grouping works as follows: We deal with the job one by one in
non-decreasing order of its processing time and pack the job into the current
group. At any time, only one group is open. When the total processing time of
jobs in the current group is at least 2, we close it and start a new group. By
doing this, all jobs in $I$ are packed into $r$ groups i.e.,
$G_{1},\dots,G_{r}$. We discard all jobs in $G_{1}$ along with
$|G_{i-1}|-|G_{i}|$ jobs with smallest processing time in $G_{i}$ for each
$i\in[2,r]$ and let it be $I_{d}$. For those remaining jobs, we lift the
processing time to the largest one among their group and let it be
$I^{\prime}$. The harmonic grouping scheme has the following property [40]:

  * •

the number of distinct job processing times in $I^{\prime}$ is at most
$\text{size}(I)/2$;

  * •

$\text{size}(I_{d})\in O(\log\text{size}(I))$.

######  Lemma 16.

$OPT_{LP}(I^{\prime})\leq OPT_{LP}(I)$

###### Proof.

Given any solution ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I)$ of instance $I$, for each
configuration we can replace each job $j$ in group $G_{i}$ with a job
$j^{\prime}$ in group $G_{i+1}$. In such a modified solution, all jobs of
$I^{\prime}$ are scheduled. Since $p_{j^{\prime}}\leq p_{j}$ holds, the
objective does not increase. ∎

Now we formally present Algorithm 3. Given an instance $I$ of the scheduling
problem, we first apply the harmonic grouping scheme to obtain the rounded
instance $I^{\prime}$ along with another instance $I_{d}$ composed by the
discarded jobs. Then we apply Lemma 14 to derive a feasible solution
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I^{\prime})$ for $I^{\prime}$
and assign jobs to machines according to
$\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I^{\prime})\rfloor$ and close
these machines. The remaining jobs
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}(I^{\prime})-\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I^{\prime})\rfloor$ and the
remaining empty machines
$m(I^{\prime})-\|\lfloor{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}(I^{\prime}_{j})\rfloor\|_{1}$
(here $\|\cdot\|_{1}$ is the 1-norm, which counts the number of integral
configurations) forms a new instance $I^{\prime}_{res}$. In the next
iteration, $I^{\prime}_{res}$ servers as the input and we repeat this process
until there are only constant machines left. For the instance with constant
machines, we call Algorithm 1. Then we do the balancing operation to make sure
that for every two machines their load difference is at most 1. At last, we
group all the discarded jobs into $O(\log^{2}m)$ groups where the total
processing time of each group is at most 2. This can be easily done, since the
processing time of each job is at most 1. We pick arbitrarily $O(\log^{2}m)$
machines and schedule each group of jobs on one machine.

Algorithm 3 Pseudo Code Description of AL3

1: $I_{D}=\emptyset$

2: while $m(I)>10$ do

3: apply harmonic grouping scheme to create instance $I^{\prime}$ and $I_{d}$

4: $I_{D}=I_{D}\cup I_{d}$

5: let $\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}(I^{\prime})$ be the
$(\epsilon/\log m)$-balanced solution for Conf-IP($I^{\prime}$)

6: schedule $I^{\prime}\setminus
I^{\prime}_{res}(\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}})$ according to
$\lfloor\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}(I^{\prime})\rfloor$

7: $I=I^{\prime}_{res}(\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}})$

8: end while

9: schedule $I$ using Algorithm 1

10: while $\exists i,j$ s.t. $L_{i}-L_{j}>1$ do

11: move the job with the largest processing time in machine $i$ to machine
$j$

12: end while

13: schedule $I_{D}$ on arbitrarily $O(\log^{2}m)$ machines with max
increasing load 2

Finally, we estimate the overall loss incurred. In each iteration, only
$m(I)/2+1$ variables take non-zero value in solution
$I^{\prime}_{res}(\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}})$. Hence,
$m(I^{\prime}_{res}(\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}))\leq m(I)/2+1$ and after at
most $O(\log m)$ rounds Algorithm 3 terminates. Each iteration introduces an
additional cost of $\varsigma$, together with discarded jobs of total
processing time $O(\log^{2}m)$, which need to be handled at last. Set
$\varsigma=O(\log m)$ and observing that $OPT\geq OPT_{LP}(I)$ and $OPT\geq
m$, we know the overall additional cost is bounded by $O(\log^{2}m)$. Now
consider all the discarded jobs. Through Lemma 1 and the balancing operation,
we know the load of machines in the solution is at most 3. Meanwhile, due to
the convexity of the objective, the balancing operation does not increase the
objective value. Given that $q$ is a constant, hence, the overall objective
value increases by at most $O(\log^{2}m)$, and Lemma 13 is proved.

##  Appendix B Omitted Proofs in Section 3.1 \- Proof of Lemma 4

The goal of this section is to prove the following lemma.

######  Lemma 4.

Assuming ETH, there exists a constant $\beta\in(0,1)$ such that for any
sufficiently small $\epsilon^{\prime},\delta>0$, it is not possible to
distinguish between instances of 3SAT$\,{}^{\prime}$ with
$(1-\epsilon^{\prime})\cdot 4n/3$ clauses where at least $4n/3$ clauses are
satisfiable, from instances where at most $(\beta+\epsilon^{\prime})\cdot
4n/3$ clauses are satisfiable, in time $2^{O(n^{1-\delta})}$.

Towards the proof, we start with the following result (see, e.g., Corollary 1
of [5]).

######  Lemma 17.

[34, 5] Under ETH, for sufficiently small $\epsilon^{\prime}>0$, and
$\delta>0$, it is impossible to distinguish between instances of 3SAT with
$\Lambda$ clauses where at least $(1-\epsilon^{\prime})\Lambda$ are
satisfiable from instances where at most $(7/8+\epsilon^{\prime})\Lambda$ are
satisfiable, in time $O(2^{\Lambda^{1-\delta}})$.

Applying the classical technique of constructing enforcer via expander for
3SAT (see, e.g., Theorem 5 of [39]), we have the following,

######  Lemma 18.

[39] There exists a constant $d_{0}$ such that given a 3SAT formula $\phi$
with $\Lambda$ clauses, another 3SAT formula $\phi^{\prime}$ with
$\Lambda^{\prime}=\Lambda+3d_{0}\Lambda=O(\Lambda)$ clauses can be constructed
in polynomial time such that:

  * •

Every variable occurs in at most $2d+1$ clauses in $\phi^{\prime}$;

  * •

There is an assignment for $\phi$ where at most $k$ clauses are not satisfied
if and only if there is an assignment for $\phi^{\prime}$ such that at most
$k$ clauses are not satisfied.

Denote by 3SAT-$d$ the 3SAT problem where every variable occurs at most $d$
times. Combining Lemma 17 and Lemma 18, we have the following lemma.

######  Lemma 19.

Under ETH, there exists some constants $d\in\mathbb{N}$ and $\alpha\in(0,1)$
such that for sufficiently small $\epsilon^{\prime}>0$, and $\delta>0$, it is
impossible to distinguish between instances of 3SAT-$d$ with $\Lambda$ clauses
where at least $(1-\epsilon^{\prime})\Lambda$ are satisfiable from instances
where at most $(\alpha+\epsilon^{\prime})\Lambda$ are satisfiable, in time
$O(2^{\Lambda^{1-\delta}})$.

It is worth mentioning that the reduction in [39] involves constructing
2-clauses, that is, 3SAT-$d$ in Lemma 19 refers to a 3SAT instance where
clauses may contain 2 or 3 variables. For ease of presentation, we want to
enforce every clause to contain exactly 3 variables222We remark, however, that
our reduction also works if $C_{1}$ contains 2-causes and 3-clauses. It
suffices to create two CLℓ, one true copy and one false copy instead of three,
and meanwhile adjust the number of dummy jobs.. This can be done by
introducing dummy variables together with 3-clauses that enforce a dummy
variable to be true or false (called enforcers). In particular, Berman et al.
[4] provide a general enforcer that allows them to deduce the APX-hardness of
MAX3SAT (where every clause contains 3 variables and every variable appears 4
times) through the APX-hardness of MAX2SAT. We can apply their technique
directly to get a strengthened version of Lemma 19 where in 3SAT-$d$ every
clause contains exactly 3 variables.

The following proof is a slight variation of that from Tovey [38].

######  Lemma 20.

Given a 3SAT-$d$ formula $\phi$ with $\Lambda$ clauses, a 3SAT$\,{}^{\prime}$
formula $\phi^{\prime}$ with $|C_{1}|=\Lambda$ and $|C_{2}|\leq 3\Lambda$
clauses can be constructed in polynomial time such that:

  * •

If there is an assignment for $\phi$ where at most $k$ clauses are not
satisfied, then there is an assignment for $\phi^{\prime}$ where at most $k$
clauses are not satisfied.

  * •

If there is an assignment for $\phi^{\prime}$ where there are at most $k$
clauses not satisfied, then there is an assignment for $\phi$ where at most
$kd$ clauses are not satisfied.

###### Proof.

Let $z$ be any variable in $\phi$ and suppose it appears $\ell\leq d$ times in
clauses. If $\ell=1$ then we add a dummy clause $(z\oplus\neg z)$. Otherwise
$\ell\geq 2$ and we introduce $\ell$ new variables $z_{1}$, $z_{2}$, $\cdots$,
$z_{\ell}$ and $\ell$ new clauses $(z_{1}\oplus\neg z_{2})$, $(z_{2}\oplus\neg
z_{3})$, $\cdots$, $(z_{\ell}\oplus\neg z_{1})$ which enforce
$z_{1},z_{2},\cdots,z_{\ell}$ to take the same truth value. Meanwhile we
replace the $\ell$ occurrences of $z$ in the original clauses by $z_{1}$,
$z_{2}$, $\cdots$, $z_{\ell}$ in turn and remove $z$. By doing so we transform
$\phi$ into a new formula $\phi^{\prime}$ by introducing at most $3\Lambda$
new variables and $3\Lambda$ new clauses.

Notice that each new clause we add in $\phi^{\prime}$ is of the form
$(z_{i}\oplus\neg z_{i^{\prime}})$. We let $C_{2}$ be the set of them and let
$C_{1}$ be the set of other clauses. It is easy to verify that $\phi^{\prime}$
is an instance of 3SAT′. Notice that every clause in $C_{1}$ has a
corresponding clause in $\phi$ by replacing $z_{i}$’s with $z$.

Suppose there is an assignment for $\phi$ where at most $k$ clauses are not
satisfied. Then for any variable $z$ in $\phi$ that occurs $\ell$ times, we
let $z_{1}$, $z_{2}$, $\cdots$, $z_{\ell}$ all take the same value as $z$. It
is easy to see that at most $k$ clauses in $C_{1}$ of $\phi^{\prime}$ are not
satisfied.

Suppose there is an assignment for $\phi^{\prime}$ where at most $k$ clauses
in $C_{1}$ are not satisfied. For any variable $z$ in $\phi$ that correspond
to $z_{1}$, $z_{2}$, $\cdots$, $z_{\ell}$ in $\phi^{\prime}$, we let $z_{i}$
take the same value of $z_{1}$ for all $i$. Now we check the number of
additional unsatisfied clauses in $C_{1}$ we introduce by doing so. If all
$z_{i}$’s take the same value, then no additional unsatisfied clauses are
introduced. Otherwise, it is possible that some of the clauses in $C_{1}$,
which is satisfied by $z_{2}$, $z_{3}$, $\cdots$ or $z_{\ell}$, becomes
unsatisfied. But there are at most $d-1$ such kind of clauses. Hence, at most
$d-1$ unsatisfied clauses are introduced, if there is at least one unsatisfied
clause among $(z_{1}\oplus\neg z_{2})$, $(z_{2}\oplus\neg z_{3})$, $\cdots$,
$(z_{\ell}\oplus\neg z_{1})$. This implies that we have introduced at most
$k(d-1)$ unsatisfied clauses by setting $z_{i}=z_{1}$ for all variables, i.e.,
there are at most $k(d-1)+k=kd$ unsatisfied clauses in $C_{1}$ now. Hence,
there is an assignment for $\phi$ where at most $kd$ clauses are not
satisfied. ∎

Given Lemma 20, we know that if there is an assignment for $\phi$ with are at
most $\alpha\Lambda$ unsatisfied clauses, then there is an assignment for
$\phi^{\prime}$ with every clause in $C_{2}$ satisfied and at most
$\alpha\Lambda$ clauses in $C_{1}$ unsatisfied; if every assignment has at
least $\beta\Lambda$ unsatisfied clauses in $\phi$, then there are at least
$\beta\Lambda/d$ unsatisfied clauses in $\phi^{\prime}$. Hence, according to
Lemma 19, Lemma 4 is proved.

##  Appendix C Omitted Contents in Section 3.2 \- Why Old Reduction does not
Work

Chen et al. [7] provided a reduction that meets the conditions CO1 to CO4 with
job processing times, and hence the target value $T$, being $O(n^{1+\delta})$
for any arbitrary small constant $\delta>0$. This reduction provides a strong
lower bound for $P||C_{max}$, but does not work well for our problem
$P||\sum_{i}C_{i}^{q}$. To see this, we take $q=2$ as an example and compare
the two objective values for the constructed scheduling problem when $I_{sat}$
is satisfiable and when it is not. If $I_{sat}$ is satisfiable, then there
exists a schedule such that every machine has a load of exactly $T$, implying
that the optimal objective value is $mT^{2}$. Otherwise, at least one machine
has load $T+1$ or more and machine has load $T-1$ or less, and then the
optimal objective is at least $(m-2)T^{2}+(T+1)^{2}+(T-1)^{2}=mT^{2}+2$. For
the sake of contradiction, let us assume that there exists a PTAS with running
time $2^{O((1/\epsilon)^{\kappa})}$ for some $\kappa\in(0,1)$. If we take
$\epsilon$ to be sufficiently small such that $mT^{2}\epsilon\leq 1$, then the
PTAS can be used to determine whether the constructed scheduling instance
admits a feasible schedule of objective value at most $mT^{2}+1<mT^{2}+2$, and
hence whether $I_{sat}$ is satisfiable. The running time of the PTAS becomes
$2^{O((1/\epsilon)^{\kappa})}=2^{O((mT^{2})^{\kappa})}$. Plug in $m=O(n)$ and
$T=O(n^{1+\delta})$ in the reduction, we have $mT^{2}=O(n^{3+2\delta})$.
Hence, if $\kappa=1/3-\delta$, we have $(mT^{2})^{\kappa}\leq
O(n^{1-\delta})$, and an efficient PTAS of running time
$2^{O((1/\epsilon)^{1/3-\delta})}$ can thus determine the satisfiability of
$I_{sat}$ in $2^{O(n^{1-\delta})}$ time, contradicting ETH. To summarize, the
above argument implies a lower bound of $2^{O((1/\epsilon)^{1/3-\delta})}$ on
the running time of PTAS for arbitrary constant $\delta>0$, which is not
strong enough to match our algorithms in Theorem 1.

To overcome the obstacle, a natural idea is to decrease the value of $m$ or
$T$ in the reduction. However, if, say, $m=n^{0.9}$ and $T=n^{O(1)}$, then we
know the standard dynamic programming for scheduling returns the optimal
solution in $T^{O(m)}=2^{O(n^{0.9})}$ time; similarly, if $T=n^{0.9}$ and
$m=n^{O(1)}$, then we know there are at most $n^{0.9}$ different kinds of
jobs, and the scheduling problem can also be solved in time $2^{O(n^{0.9})}$
through dynamic programming. Hence, we cannot expect to reduce $I_{sat}$ to
such scheduling instances, assuming ETH.

As a consequence, in this paper, we will not try to decrease $m$ or $T$.
Instead, we increase the gap between the two optimal objective values for the
constructed scheduling problem when $I_{sat}$ is satisfiable and when
$I_{sat}$ is not satisfiable by exploiting the hardness gap in Lemma 4.

##  Appendix D Omitted Proofs in Section 3.4 \- Proof of Lemma 5

######  Lemma 5.

Let $N\in\mathbb{Z}^{+}$. There exists a subset
${\cal{S}}\subseteq\mathbb{Z}_{N}$ such that $|{\cal{S}}|\geq
N^{1-c_{0}\sqrt{\frac{1}{{\log N}}}}$ for some sufficiently large $c_{0}$ (in
particular, $c_{0}=7$ suffices), and for any $y\in{\cal{S}}$ and $1\leq h\leq
5$, the linear equation $h\cdot y=y_{1}+y_{2}+\cdots+y_{h}$ with
$y_{i}\in{\cal{S}}$ for all $i$ has a unique solution
$y_{1}=y_{2}=\cdots=y_{h}=y$.

###### Proof.

For any $d\geq 2$, $M\geq 2$ and $k\leq(M+1)(d-1)^{2}$, we let $x=5d-1$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}=(1,x,x^{2},\cdots,x^{M})$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[M])$. We define the set
$S_{k}(M,d)$ as:

$\displaystyle{\cal{S}}_{k}(M,d)$ $\displaystyle=$
$\displaystyle\\{y:y={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}+x^{M+1}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}[0]+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}[1]x^{1}+\cdots+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[M]x^{M}+x^{M+1},$
$\displaystyle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}[i]\in\mathbb{N},0\leq{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}[i]<d,\sum_{i=0}^{M}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[i])^{2}=k\\}.$

That is, ${\cal{S}}_{k}(M,d)$ is the set of all integers which can be
expressed in the form of ${{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}}\cdot{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}+x^{M+1}$ such that
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[i]\in[0,d)$ and
$\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}\|_{2}^{2}=k$, where
$\|\cdot\|_{2}$ is the $\ell_{2}$-norm of a vector.

We claim that for any $y\in{\cal{S}}_{k}(M,d)$ and $1\leq h,h^{\prime}\leq 5$,
if $hy=y_{1}+y_{2}+\cdots+y_{h^{\prime}}$, $y_{i}\in S_{k}(M,d)$, then we have
$h^{\prime}=h$, $y_{1}=y_{2}=\cdots=y_{h}=y$. Let
$y={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+x^{M+1}$ and
$y_{j}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+x^{M+1}$, where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}[2],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[M])$. Using the fact that
$x=5d-1$ and ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[i]<d$, we know for
$h^{\prime}\leq 5$ we have
$\sum_{j=1}^{h^{\prime}}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[i]<x$. Hence by checking
the coefficient of $x^{M+1}$ on both sides of the equation
$hy=\sum_{j=1}^{h^{\prime}}y_{j}$, we have $h=h^{\prime}$. Moreover, we can
conclude that the coefficient of $x^{i}$ in the sum
$y_{1}+y_{2}+\cdots+y_{h^{\prime}}$ equals
$\sum_{j=1}^{h^{\prime}}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[i]$, hence by comparing
the coefficient of $x^{i}$ on both sides, we have

$\sum_{j=1}^{h}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}=h{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}.$

By the definition of ${\cal{S}}_{k}(M,d)$, the followings are true:

$\sum_{i=0}^{M}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[i])^{2}=k,\quad\forall
j,$

and

$\sum_{i=0}^{M}(\frac{\sum_{j=1}^{h}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}[i]}{h})^{2}=\sum_{i=0}^{M}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[i])^{2}=k$

Hence,

$\displaystyle
k=\sum_{i=0}^{M}(\frac{\sum_{j=1}^{h}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}[i]}{h})^{2}=\frac{\sum_{j=1}^{h}\sum_{i=0}^{M}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}[i])^{2}}{h}=\sum_{i=0}^{M}\frac{\sum_{j=1}^{h}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[i])^{2}}{h}.$ (6)

According to the inequality between the quadratic mean and arithmetic mean, we
know

$\left(\frac{\sum_{j=1}^{h}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{j}[i]}{h}\right)^{2}\leq\frac{\sum_{j=1}^{h}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}[i])^{2}}{h},\quad\forall
i$

and the equality only holds when $c_{j}[i]$’s are identical for all $j$. Hence
by Eq (6) we know ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}$, and consequently
$y_{j}=y$ for $1\leq j\leq h$. Hence, the claim is true.

It remains to select an appropriate ${\cal{S}}_{k}(M,d)$ such that
${\cal{S}}_{k}\subseteq\mathbb{Z}_{N}$ and has a large cardinality. Towards
this, we first observe that the largest number of ${\cal{S}}_{k}(M,d)$ is
bounded by $(5d-1)^{M+2}$. We shall select $d$ and $M$ such that
$(5d-1)^{M+2}\leq N$. Notice that there are $d^{M+1}-1$ different positive
integer numbers which can be expressed as
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+x^{M+1}$ where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[i]\in[0,d)$. Furthermore
$k=\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}\|_{2}^{2}\leq(M+1)(d-1)^{2}$,
hence there exists some $1\leq k^{*}\leq(M+1)(d-1)^{2}$ such that

$|{\cal{S}}_{k^{*}}({M,d})|\geq\frac{d^{M+1}-1}{(M+1)(d-1)^{2}}>\frac{d^{M-1}}{M+1}.$

It remains to select $d$ and $M$ subject to $(5d-1)^{M+2}\leq N$ such that
$\frac{d^{M-1}}{M+1}$ is large. Below all logarithms are taken with the base
$e$. We pick $M=\lfloor\sqrt{\frac{\log N}{\log 5}}\rfloor-2$ and
$d=\lfloor\frac{e^{\sqrt{\log 5\cdot\log N}}}{5}\rfloor$. It is easy to see
that $(M+2)\log(5d-1)\leq\sqrt{\frac{\log N}{\log 5}}\cdot\log e^{\sqrt{\log
5\cdot\log N}}=\log N$, hence $(5d-1)^{M+2}\leq N$. Furthermore, for
sufficiently large $N$ (e.g., $N>e^{10}$), we know $d\geq\frac{e^{\sqrt{\log
5\cdot\log N}}}{10}$, hence

$\displaystyle\frac{d^{M-1}}{M+1}=e^{(M-1)\log d-\log(M+1)}$
$\displaystyle\geq$ $\displaystyle e^{(\sqrt{\log N\cdot\log 5}-\log
10)(\sqrt{\frac{\log N}{\log 5}}-4)-\frac{1}{2}(\log\log N-\log\log 5)}$
$\displaystyle\geq$ $\displaystyle e^{\log N\cdot(1+\frac{-4\sqrt{\log N\log
5}-\frac{\log 10}{\sqrt{\log 5}}\sqrt{\log N}-\Omega(\log\log N)}{\log N})}$
$\displaystyle=$ $\displaystyle N^{1-\Omega(\frac{1}{\sqrt{\log N}})}$

Hence, Lemma 5 is proved. In particular, it is easy to verify that
$4\sqrt{\log 5}+\frac{\log 10}{\sqrt{\log 5}}\leq 7$, hence the
$\frac{d^{M-1}}{M+1}\geq N^{1-\frac{7}{\sqrt{\log N}}}$. ∎

##  Appendix E Omitted proofs in Section 3.4 \- Proof of Lemma 7

The goal of this subsection is to prove the following.

######  Lemma 8.

For any $\pi\in Aut({\cal{M}}^{\upsilon})$, there exist $h$-shufflers
$f_{h},\hat{f}_{h}\in Aut({\cal{M}}^{\upsilon})$ for every $1\leq
h\leq\upsilon$ such that $F({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\hat{F}(\pi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}))$ for any
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$,
where $F=f_{\upsilon-1}\circ f_{\upsilon-2}\circ\cdots\circ f_{0}$ and
$\hat{F}=\hat{f}_{\upsilon-1}\circ\hat{f}_{\upsilon-2}\circ\cdots\circ\hat{f}_{0}$.
Furthermore, $f_{h}$’s and $\hat{f}_{h}$’s can be constructed in time that is
polynomial in $|{\cal{M}}^{\upsilon}|$.

For any finite set $X$, we denote by $Aut(X)$ the set of all one-to-one
mapping from $X$ to itself. For any $f_{1},f_{2}\in Aut(X)$, we denote by
$f_{1}\circ f_{2}\in Aut(X)$ the composition of $f_{1}$ and $f_{2}$, i.e.,
$f_{1}\circ f_{2}(x)=f_{1}(f_{2}(x))$ for any $x\in X$. Note that $Aut(X)$ is
a symmetric group under composition. We denote by $f^{-1}\in Aut(X)$ the
inverse of $f\in Aut(X)$.

Let ${\cal{M}}$ be an arbitrary finite set of cardinality $t$. Let
$\upsilon\in\mathbb{Z}^{+}$. Denote by ${\cal{M}}^{\upsilon}$ the set of all
$\upsilon$-dimensional vectors whose entries belong to ${\cal{M}}$.

For any vector ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$, we
denote by ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}[h]\in{\cal{M}}$ the $h$-th
coordinate of $\textstyle\bf y$, and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}[-h]\in{\cal{M}}^{\upsilon-1}$
the vector obtained by removing the $h$-th coordinate from $\textstyle\bf y$.

For any $f\in Aut({\cal{M}}^{\upsilon})$ and $0\leq h\leq\upsilon-1$, we call
$f$ an $h$-shuffler if $\left(f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\right)[-h]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}[-h]$ for all
$y\in\cal{M}^{\upsilon}$, that is,

$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[0],{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[\upsilon-1])=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[0],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[h-1],z,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}[h+1],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}[\upsilon-1])),$

for some $z\in{\cal{M}}$.

We prove the following lemma.

######  Lemma 21.

For any $\pi\in Aut({\cal{M}}^{\upsilon})$ and $0\leq h\leq\upsilon-1$, there
exist $h$-shufflers $f,\hat{f}\in Aut({\cal{M}}^{\upsilon})$ such that for any
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$,
$\left(f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\right)[h]=\left(\hat{f}(\pi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}))\right)[h]$. Furthermore,
$f$ and $\hat{f}$ can be constructed in time that is polynomial in
$|{\cal{M}}^{\upsilon}|$.

Figure 2: Illustration of Lemma 21 for $M=\\{1,2,3\\}$, $\upsilon=4$, $h=1$
(recall that vectors start with the $0$-th coordinate). Each vertex in $U$
(i.e., the solid circle) is a 4-dimensional vector. Each mega-vertex in
$\bar{U}$ (i.e., the dotted circle) contains exactly 3 vertices. Each solid
line between vertices represents the mapping $\pi$ which is colored by one of
3 colors.

Briefly speaking, $f$ and $\hat{f}$ shuffles the $h$-coordinate of
$\textstyle\bf y$ and its image under $\pi$ such that they become identical.

Now we are ready to prove Lemma 8.

###### Proof of Lemma 8.

For ease of presentation, we let ${\cal{M}}=\\{1,2,\cdots,t\\}$. Note that
$|{\cal{M}}^{\upsilon}|=t^{\upsilon}$. Sort elements (vectors) of
${\cal{M}}^{\upsilon}$ in an arbitrary order and denote them by
$\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{1},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{2},\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{t^{\upsilon}}\\}$. We create
a bipartite graph $G=(U\cup W,E)$ to represent $\pi$ as follows: Both $U$ and
$W$ contain $t^{\upsilon}$ vertices. Let
$U=\\{u_{1},u_{2},\cdots,u_{t^{\upsilon}}\\}$ and
$W=\\{w_{1},w_{2},\cdots,w_{t^{\upsilon}}\\}$. There is an edge between
$u_{i}$ and $w_{j}$ if and only if
$\pi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{i})={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}$. Since $\pi$ is one-to-
one mapping, $G$ is 1-regular.

As each $u_{i}$ and $w_{i}$ correspond to
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{i}$, we will slightly abuse
notation and write $u_{i}[h]$ or $u_{i}[-h]$ to refer to
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{i}[h]$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{i}[-h]$.

Contraction. We contract the graph $G$ as follows. We partition $U$ (or $W$)
into $t^{\upsilon-1}$ subsets such that $u_{i}$ and $u_{j}$ (or $w_{i}$ and
$w_{j}$) are in the same subset if and only if $u_{i}[-h]=u_{j}[-h]$ (or
$w_{i}[-h]=w_{j}[-h]$). Denote by $\bar{U}_{i}$ (or $\bar{W}_{i}$), $1\leq
i\leq t^{\upsilon-1}$, all the subsets in the partition of $U$ (or $W$). It is
clear that each $\bar{U}_{i}$ (or $\bar{W}_{i}$) contains exactly $t$ vertices
from $U$ (or $W$). We now contract all the $t$ vertices in $\bar{U}_{i}$ (or
$\bar{W}_{i}$) into one mega-vertex, and denote this mega-vertex as
$\bar{u}_{i}$ (or $\bar{w}_{i}$). By doing so we generate parallel edges, that
is, there are $\ell$ parallel edges between each pair of mega-vertices
$\bar{u}_{i}$ and $\bar{w}_{j}$ if there are $\ell$ edges between vertices in
$\bar{U}_{i}$ and $\bar{W}_{j}$ in the original graph $G$. We denote by $\psi$
an arbitrary one-to-one mapping between a parallel edge (between mega-vertices
$\bar{u}_{i}$ and $\bar{w}_{j}$) and an edge in $G$ (between some vertex in
subset $\bar{U}_{i}$ and some vertex in subset $\bar{W}_{j}$). Denote by
$\bar{G}=(\bar{U}\cup\bar{W},\bar{E})$ the contracted graph. Given that $G$ is
$1$-regular and every mega-vertex contains exactly $t$ vertices, we have the
following observation:

######  Observation 4.

The contracted graph $\bar{G}=(\bar{U}\cup\bar{W},\bar{E})$ is a $t$-regular
bipartite graph.

Coloring. It is known that every bipartite regular graph admits a perfect
matching (see, e.g. [26]). Consequently, every $t$-regular bipartite graph can
be decomposed into $t$ perfect matchings. We decompose $\bar{G}$ into $t$
perfect matchings and color edges in each perfect matching with a distinct
color. Overall we have used $t$ colors. Since $|{\cal{M}}|=t$, we can map the
$i$-th color to integer $i\in{\cal{M}}$.

Recall that $\psi$ is a one-to-one mapping between $\bar{E}$ and $E$, hence
via $\psi$ we also obtain a coloring for $E$ (by coloring each edge in $E$
with the same color as its corresponding edge in $\bar{E}$). Recall that $G$
is 1-regular. Thus we can extend the edge coloring to a vertex coloring, such
that each vertex in $G$ is colored with the same color as the unique edge
incident to it.

Define functions $f$ and $\hat{f}$. Consider every vertex set $\bar{U}_{k}$.
We know $\bar{U}_{k}$ contains $t$ vertices, and let
$\bar{U}_{k}=\\{u_{k_{1}},u_{k_{2}},\cdots,u_{k_{t}}\\}$. By definition
$u_{k_{i}}[-h]$’s are identical and $u_{k_{i}}[h]$’s are exactly the $t$
elements in ${\cal{M}}$. Recall that we decompose $\bar{G}$ into $t$ perfect
matchings and each perfect matching is colored with a unique color, we know
the $t$ parallel edges incident to the mega-vertex $\bar{u}_{k}$ are colored
with $t$ distinct colors. Consequently, each vertex $u_{k_{i}}$ is also
colored with a distinct color. Recall the one-to-one correspondence between a
vertex $u_{j}$ and ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{j}\in{\cal{M}}$. Now we
define a function $f$ such that
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{i}})[-h]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{i}}[-h]$, and
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{i}})[h]$ equals the color
of $u_{k_{i}}$, where we interpret each color as a number in
$\\{1,\cdots,t\\}$. Consequently,
$(f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{1}}),f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{2}}),\cdots,f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{t}}))$ is a permutation
of $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{1}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{2}},\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{t}})$. Hence, $f\in
Aut({\cal{M}}^{\upsilon})$.

Similarly, we consider each
$\bar{W}_{k}=\\{w_{k_{1}},w_{k_{2}},\cdots,w_{k_{t}}\\}$ and define a function
$\hat{f}$ such that $\hat{f}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{i}})[-h]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{i}}[-h]$, and
$\hat{f}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{i}})[h]$ equals the color
of $w_{k_{i}}$. Consequently,
$(\hat{f}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{1}}),\hat{f}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{2}}),\cdots,\hat{f}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{t}}))$ is also a
permutation of $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{1}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf
c$}}}_{k_{2}},\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}_{k_{t}})$, and $\hat{f}\in
Aut({\cal{M}}^{\upsilon})$.

Furthermore, the color of each $u_{i}$ or $w_{j}$ is defined as the color of
the edge incident to it, hence if there is an edge between $u_{i}$ and $w_{j}$
in $G$, then we know $(f(u_{i}))[h]=(\hat{f}(w_{j}))[h]$. Hence, Lemma 21 is
proved. ∎

See Figure 2 for an illustration of the mapping $f,\hat{f}$ we construct in
Lemma 21. Iteratively applying Lemma 21, we are able to prove the following.

###### Proof.

We prove the following statement by induction: For $0\leq k\leq\upsilon-1$,
there exist $h$-shufflers $f_{h},\hat{f}_{h}\in Aut({\cal{M}}^{\upsilon})$ for
every $0\leq h\leq k$ such that
$F_{k}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})[h^{\prime}]=\hat{F}_{k}(\pi({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}))[h^{\prime}]$ for any
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$ and
$h^{\prime}\leq k$, where $F_{k}=f_{k}\circ f_{k-1}\circ\cdots\circ f_{0}$ and
$\hat{F}_{k}=\hat{f}_{k}\circ\hat{f}_{k-1}\circ\cdots\circ\hat{f}_{0}$.

The statement is true for $k=1$ by Lemma 21. Suppose the statement is true for
$k$, we prove it is true for $k+1$.

Consider
$\hat{f}_{k}\circ\hat{f}_{k-1}\circ\cdots\circ\hat{f}_{0}\circ\pi\circ
f_{0}^{-1}\circ f_{1}^{-1}\circ\cdots\circ f_{k}^{-1}$. According to Lemma 21,
there exist $(k+1)$-shufflers $f_{k+1},\hat{f}_{k+1}$ such that

$\displaystyle\left(f_{k+1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\right)[k+1]=\left(\left(\hat{f}_{k+1}\circ\hat{f}_{k}\circ\cdots\circ\hat{f}_{0}\circ\pi\circ
f_{0}^{-1}\circ f_{2}^{-1}\circ\cdots\circ
f_{k}^{-1}\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\right)[k+1],\quad\forall{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}.$ (7)

Since $f_{k}\circ f_{k-1}\circ\cdots\circ f_{1}\in Aut({\cal{M}}^{\upsilon})$,
for every ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in{\cal{M}}^{\upsilon}$ there
exists some ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in{\cal{M}}^{\upsilon}$ such
that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}=\left(f_{k}\circ
f_{k-1}\circ\cdots\circ
f_{1}\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$, plug this into Equation
(7), for all ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in{\cal{M}}^{\upsilon}$ we
get

$\displaystyle\left(f_{k+1}\circ f_{k}\circ\cdots\circ
f_{0}\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})[k+1]$ $\displaystyle=$
$\displaystyle\left(\left(\hat{f}_{k+1}\circ\cdots\circ\hat{f}_{0}\circ\pi\circ
f_{0}^{-1}\circ\cdots\circ f_{k}^{-1}\circ f_{k}\circ f_{k-1}\circ\cdots\circ
f_{0}\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\right)[k+1]$
$\displaystyle=$
$\displaystyle\left(\left(\hat{f}_{k+1}\circ\cdots\circ\hat{f}_{0}\circ\pi\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\right)[k+1]$

Moreover, for any $h\leq k$, recall that $f_{k+1}$ and $\hat{f}_{k+1}$ does
not change the $h$-th coordinate, hence

$\displaystyle\left(f_{k+1}\circ f_{k}\circ\cdots\circ
f_{0}\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})[h]$ $\displaystyle=$
$\displaystyle\left(f_{k}\circ\cdots\circ
f_{0}\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})[h]$ $\displaystyle=$
$\displaystyle\left(\left(\hat{f}_{k}\circ\cdots\circ\hat{f}_{1}\circ\pi\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\right)[h]$ $\displaystyle=$
$\displaystyle\left(\left(\hat{f}_{k+1}\circ\hat{f}_{k}\circ\cdots\circ\hat{f}_{0}\circ\pi\right)({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\right)[h]$

Hence, the statement holds for all $k\leq\upsilon-1$, and Lemma 8 is proved. ∎

##  Appendix F Construction of the Scheduling Instance

Now we provide the details of the reduction. We first recall all the functions
and parameters we have set in proving Lemma 7.

  * •

Recall that $\tau$ is the one-to-one mapping that maps $i$ to $k$ for every
$(z_{i}\oplus\neg z_{k})\in C_{2}$.

  * •

Apply Lemma 6 by taking $N=n$, we get
$\sigma:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n^{\prime}}$ where
$n^{\prime}=n^{1+{\mathcal{O}}(\frac{1}{\sqrt{\log\log n}})}$,
$\sigma(i)=\sum_{j=0}^{\gamma}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]x^{j}$ for
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[j]\in{\cal{S}}_{d}$ where
$\gamma=\lceil\frac{\log n}{\log\log n}\rceil+O(\frac{\log n}{(\log\log
n)^{3/2}})$, $d=e^{{\mathcal{O}}(\sqrt{\log\log n})}\log n$ and $x=5d+1$. We
lift the dimension such that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}=({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0],\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[\gamma+3])$ where
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[\gamma+1]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[\gamma+2]={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}[\gamma+3]=0$.

  * •

Apply Lemma 6 again by setting $N=4\gamma+4$, we get another injection
$\sigma^{\prime}$ such that $\sigma^{\prime}(y)=o(\log^{2}n)<x^{2}$ for $y\leq
4\gamma+4$.

  * •

We have constructed in the proof of Lemma 7:
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{0}_{i}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{1}_{i},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2}_{i},\cdots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2\gamma+2}_{i}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+2}_{k}$,
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+1}_{k}$, $\cdots$,
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{1}_{k},\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{0}_{k}={\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{k}$ where $k=\tau(i)$.

  * •

Again, each vector $\textstyle\bf c$ represents the polynomial
$\sum_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
c$}}{\mbox{\boldmath$\textstyle\bf c$}}{\mbox{\boldmath$\scriptstyle\bf
c$}}{\mbox{\boldmath$\scriptscriptstyle\bf c$}}}[i]x^{i}$. Polynomials and
vectors are used interchangeably.

  * •

Let $\sigma_{max}=x^{\gamma+6}=n^{1+O(\frac{1}{\sqrt{\log\log n}})}$, and thus
$\sigma_{max}>x\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ and
$\sigma_{max}>x\cdot\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ for any $i,h$, and also
$\sigma_{max}>\sigma^{\prime}(y)x^{\gamma+3}$ for any $y\leq 4\gamma+4$.

Construction of the scheduling instance. We shall construct two major classes
of jobs, gap jobs and main jobs. Main jobs are divided into $5$ types: dummy
jobs, clause jobs, truth-assignment jobs, link jobs and variable jobs. The
three types – truth-assignment, link and variable jobs – are further divided
into sub-types, e.g., variable jobs are further divided into 4 sub-types (see
Table 1). A gap job is defined as a fixed huge value $10^{14}\sigma_{max}$
subtracting several main jobs.

The processing time of each job can be expressed as a summation over three
components: Type, Index and True/False. The type component of a main job is
always of the form $10^{j}\sigma_{max}$ where $2\leq j\leq 13$. Table 1
summarizes the value $j$ for each kind of main job, e.g., the type-component
of a variable job whose sub-type belongs to V⋅,+,1 is $10^{5}\sigma_{max}$.
The index-component of clause jobs, truth-assignment jobs and variable jobs is
of the form $10\sigma(i)$ for some index $i$. Dummy jobs do not have index-
component; Link jobs have much more complicated index-components, which will
be specified in the following part of this subsection. Each main job has a
true version and a false version. A gap job does not have a true/false version
but only one unified version.

$\backslash$ | Dummy | Clause | Truth-assignment | Link | Variable
---|---|---|---|---|---
$\backslash$ | DM | CL⋅ | TR⋅,a | TR⋅,b | TR⋅,c | TR⋅,d | LN⋅,+ | LN⋅,- | V⋅,+,1 | V⋅,+,2 | V⋅,-,1 | V⋅,-,2
$\zeta(\cdot)$ | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2

Table 1: Type-component of main jobs

Define a function $\zeta$ that maps the (sub)-type of a main job to the
exponent of $10$ as indicated by Table 1, e.g.,
$\zeta(\textrm{TR}_{\cdot,a})=11$. Now we provide the exact processing time of
every job. In the following $\rho\in\\{T,F\\}$, $\iota\in\\{+,-\\}$.

$\bullet$ Variable jobs: 4 jobs $V_{i,+,1}^{\rho}$ and $V_{i,+,2}^{\rho}$ are
constructed for the positive literal $z_{i}$, and 4 jobs $V_{i,-,1}^{\rho}$
and $V_{i,-,2}^{\rho}$ are for the negative literal $\neg z_{i}$.

$\displaystyle
s(V_{i,\iota,\kappa}^{T})=10^{\zeta(\textrm{V}_{\cdot,\iota,k})}\sigma_{max}+10\sigma(i)+1,$
$\displaystyle
s(V_{i,\iota,\kappa}^{F})=10^{\zeta(\textrm{V}_{\cdot,\iota,k})}\sigma_{max}+10\sigma(i)+2,\quad\kappa=1,2,\iota=+,-$

$\bullet$ Truth-assignment jobs: 8 jobs $\textrm{TR}_{i,a}^{\rho}$,
$\textrm{TR}_{i,b}^{\rho}$, $\textrm{TR}_{i,c}^{\rho}$ and
$\textrm{TR}_{i,d}^{\rho}$ are constructed for every $i$.

$\displaystyle
s(\textrm{TR}_{i,\kappa}^{T})=10^{\zeta(\textrm{TR}_{\cdot,\kappa})}\sigma_{max}+10\sigma(i)+1.5,$
$\displaystyle
s(\textrm{TR}_{i,\kappa}^{F})=10^{\zeta(\textrm{TR}_{\cdot,\kappa})}\sigma_{max}+10\sigma(i)+1.\quad\kappa=a,b,c,d$

$\bullet$ Clause jobs: there are 3 clause jobs for every clause $cl_{\ell}\in
C_{1}$ where $\ell\in\\{2,5,\cdots,n-1\\}$, with one $\textrm{CL}_{\ell}^{T}$
and two copies of $\textrm{CL}_{\ell}^{F}$:

$s(\textrm{CL}_{\ell}^{T})=10^{\zeta(\textrm{CL}_{\cdot})}\sigma_{max}+10\sigma(\ell)+2,\quad
s(\textrm{CL}_{\ell}^{F})=10^{\zeta(\textrm{CL}_{\cdot})}\sigma_{max}+10\sigma(\ell)+1.$

$\bullet$ Dummy jobs: there are $n+n/3$ true dummy jobs $\textrm{DM}^{T}$ of
processing time $10^{\zeta(\textrm{DM})}\sigma_{max}+1$, and $n-n/3$ false
dummy jobs $\textrm{DM}^{F}$ of processing time
$10^{\zeta(\textrm{DM})}\sigma_{max}+2$.

$\bullet$ Link jobs: We create $4\gamma+4$ links jobs for each clause in
$C_{2}$. Recall the vectors ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}$ and
$\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{h}_{i}$ for $1\leq h\leq
2\gamma+2$. For every clause $(z_{i}\oplus z_{k})\in C_{2}$ and every $1\leq
h\leq 2\gamma+2$, we create two pairs of link jobs, LN${}_{i,h,+}^{T}$ and
LN${}_{i,h,+}^{F}$, and LN${}_{k,h,-}^{T}$ and LN${}_{k,h,-}^{F}$ such that

$s(\textrm{LN}_{i,h,+}^{T})=10^{\zeta(\textrm{LN}_{\cdot,+})}\sigma_{max}+10{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}(i){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+1,\quad
s(\textrm{LN}_{i,h,+}^{F})=10^{\zeta(\textrm{LN}_{\cdot,+})}\sigma_{max}+10{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+2,$
$s(\textrm{LN}_{k,h,-}^{T})=10^{\zeta(\textrm{LN}_{\cdot,-})}\sigma_{max}+10\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h}(k){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+1,\quad
s(\textrm{LN}_{k,h,-}^{F})=10^{\zeta(\textrm{LN}_{\cdot,-})}\sigma_{max}+10\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h}(i){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}+2.$

Let $\textrm{TR}_{A}$, $\textrm{TR}_{B}$, $\textrm{TR}_{C}$, $\textrm{TR}_{D}$
be the set of jobs $\textrm{TR}_{i,a}^{\rho}$, $\textrm{TR}_{i,b}^{\rho}$,
$\textrm{TR}_{i,c}^{\rho}$ and $\textrm{TR}_{i,d}^{\rho}$ respectively.
Sometimes we may drop the superscript for simplicity, e.g., we use
$\textrm{TR}_{i,a}$ to represent $\textrm{TR}_{i,a}^{T}$ or
$\textrm{TR}_{i,a}^{F}$. We construct gap jobs. There are 5 kinds of gap jobs.

$\bullet$ There are two gap jobs (variable-link jobs)
$\theta_{\textrm{LN},i,+}$ and $\theta_{\textrm{V-L},i,-}$ for each variable
$z_{i}$:

$\displaystyle s(\theta_{\textrm{V-L},i,+})$ $\displaystyle=$
$\displaystyle(10^{14}-10^{7}-10^{4})\sigma_{max}-10\left({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0]+2\sum_{j=1}^{\gamma}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]x^{j}+(F_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0]\cdot
x^{\gamma+1}+{\sigma}^{\prime}(1)x^{\gamma+2}\right)-3$ $\displaystyle=$
$\displaystyle\left(10^{14}-10^{\zeta(\textrm{LN}_{\cdot,+})}-10^{\zeta(V_{\cdot,+,2})}\right)\sigma_{max}-10({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{1}_{i}){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}-3$ $\displaystyle
s(\theta_{\textrm{V-L},i,-})$ $\displaystyle=$
$\displaystyle(10^{14}-10^{6}-10^{2})\sigma_{max}-10\left({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[0]+2\sum_{j=1}^{\gamma}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}[j]x^{j}+(\hat{F}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}))[0]\cdot
x^{\gamma+1}+{\sigma}^{\prime}(1)x^{\gamma+2}\right)-3$ $\displaystyle=$
$\displaystyle\left(10^{14}-10^{\zeta(\textrm{LN}_{\cdot,-})}-10^{\zeta(V_{\cdot,-,2})}\right)\sigma_{max}-10\left({\mathchoice{\mbox{\boldmath$\displaystyle\bf
a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf
a$}}{\mbox{\boldmath$\scriptscriptstyle\bf
a$}}}_{i}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{1}_{i}\right){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}-3$

$\bullet$ There are $4\gamma+3$ gap jobs (link-link jobs),
$\theta_{\textrm{L-L},i,h,+}$ and $\theta_{\textrm{L-L},i,h,-}$ and
$\theta_{\textrm{L-L},i,+,-}$ for every $1\leq i\leq n$. For
$h=1,2,\cdots,2\gamma+1$, we define

$\displaystyle s(\theta_{\textrm{L-L},i,h,+})$ $\displaystyle=$
$\displaystyle\left(10^{14}-2\times
10^{\zeta(\textrm{LN}_{\cdot,+})}\right)\sigma_{max}-10\left({\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h+1}_{i}\right){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}-3$ $\displaystyle
s(\theta_{\textrm{L-L},i,h,-})$ $\displaystyle=$
$\displaystyle\left(10^{14}-2\times
10^{\zeta(\textrm{LN}_{\cdot,-})}\right)\sigma_{max}-10\left(\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}}^{h+1}_{i}\right){\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}-3$

Additionally, we define

$\displaystyle
s(\theta_{\textrm{L-L},i,+,-})=\left(10^{14}-10^{\zeta(\textrm{LN}_{\cdot,+})}-10^{\zeta(\textrm{LN}_{\cdot,-})}\right)\sigma_{max}-2\times
10{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2\gamma+2}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}-3$

Here recall that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{2\gamma+2}_{i}=\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{2\gamma+2}_{\tau(i)}$.

$\bullet$ There are three gap jobs (variable-clause-dummy jobs) for each
$cl_{\ell}\in C_{1}$ ($\ell\in\\{2,5,\cdots,n-1\\}$): for
$i=\ell-1,\ell,\ell+1$, if $z_{i}\in cl_{\ell}$, we construct
$\theta_{\textrm{V-C-D},\ell,i,+}$, otherwise $\neg z_{i}\in cl_{\ell}$, and
we construct $\theta_{\textrm{V-C-D},\ell,i,-}$:

$\displaystyle
s(\theta_{\textrm{V-C-D},\ell,i,+})=\left(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(\textrm{CL}_{\cdot})}-10^{\zeta(V_{\cdot,+,1})}\right)\sigma_{max}-10(\sigma(\ell)+\sigma(i))-4,$
$\displaystyle
s(\theta_{\textrm{V-C-D},\ell,i,-})=\left(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(\textrm{CL}_{\cdot})}-10^{\zeta(V_{\cdot,-,1})}\right)\sigma_{max}-10(\sigma(\ell)+\sigma(i))-4.$

$\bullet$ There is one gap job (variable-dummy job) for each variable. Notice
that each variable appears exactly once in clauses of $C_{1}$, if $z_{i}$
appears in $C_{1}$, we construct $\theta_{\textrm{V-D},i,-}$. Otherwise, we
construct $\theta_{\textrm{V-D},i,+}$ instead.

$\displaystyle
s(\theta_{\textrm{V-D},i,+})=\left(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(V_{\cdot,+,1})}\right)\sigma_{max}-10\sigma(i)-3,$
$\displaystyle
s(\theta_{\textrm{V-D},i,-})=\left(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(V_{\cdot,-,1})}\right)\sigma_{max}-10\sigma(i)-3.$

Thus, for each clause $cl_{\ell}$ and $i=\ell-1,\ell,\ell+1$, either
$\theta_{\textrm{V-D},i,+}$ and $\theta_{\textrm{V-C-D},\ell,i,-}$ exist, or
$\theta_{\textrm{V-D},i,-}$ and $\theta_{\textrm{V-C-D},\ell,i,+}$ exist.

$\bullet$ There are four gap jobs (variable-truth jobs) for each variable
$z_{i}$, namely $\theta_{\textrm{V-T},i,a,c}$, $\theta_{\textrm{V-T},i,b,d}$,
$\theta_{\textrm{V-T},i,a,d}$ and $\theta_{\textrm{V-T},i,b,c}$:

$\displaystyle
s(\theta_{\textrm{V-T},i,a,c})=\left(10^{14}-10^{\zeta(V_{\cdot,+,1})}-10^{\zeta(\textrm{TR}_{\cdot,a})}-10^{\zeta(\textrm{TR}_{\cdot,c})}\right)\sigma_{max}-30\sigma(i)-4,$
$\displaystyle
s(\theta_{\textrm{V-T},i,b,d})=\left(10^{14}-10^{\zeta(V_{\cdot,+,2})}-10^{\zeta(\textrm{TR}_{\cdot,b})}-10^{\zeta(\textrm{TR}_{\cdot,d})}\right)\sigma_{max}-30\sigma(i)-4,$
$\displaystyle
s(\theta_{\textrm{V-T},i,a,d})=\left(10^{14}-10^{\zeta(V_{\cdot,-,1})}-10^{\zeta(\textrm{TR}_{\cdot,a})}-10^{\zeta(\textrm{TR}_{\cdot,d})}\right)\sigma_{max}-30\sigma(i)-4,$
$\displaystyle
s(\theta_{\textrm{V-T},i,b,c})=\left(10^{14}-10^{\zeta(V_{\cdot,-,2})}-10^{\zeta(\textrm{TR}_{\cdot,b})}-10^{\zeta(\textrm{TR}_{\cdot,c})}\right)\sigma_{max}-30\sigma(i)-4,$

Overall, we have constructed $2\gamma n+8n$ gap jobs. We also construct
$2\gamma n+8n$ machines. The following Table 2 summarizes the processing times
of all jobs.

Job-type | Sub-type | Type-component | Index-component |  T/F (T) |  T/F (F)
---|---|---|---|---|---
Variable | $V_{i,+,1}$ | $10^{\zeta(\textrm{V}_{\cdot,+,1})}\sigma_{max}$ | $10\sigma(i)$ | 1 | 2
$V_{i,+,2}$ | $10^{\zeta(\textrm{V}_{\cdot,+,2})}\sigma_{max}$ | $10\sigma(i)$ | 1 | 2
$V_{i,-,1}$ | $10^{\zeta(\textrm{V}_{\cdot,-,1})}\sigma_{max}$ | $10\sigma(i)$ | 1 | 2
$V_{i,-,2}$ | $10^{\zeta(\textrm{V}_{\cdot,-,2})}\sigma_{max}$ | $10\sigma(i)$ | 1 | 2
Truth-assignment | TRi,a | $10^{\zeta(\textrm{TR}_{\cdot,a})}\sigma_{max}$ | $10\sigma(i)$ | 1.5 | 1
TRi,b | $10^{\zeta(\textrm{TR}_{\cdot,b})}\sigma_{max}$ | $10\sigma(i)$ | 1.5 | 1
TRi,c | $10^{\zeta(\textrm{TR}_{\cdot,c})}\sigma_{max}$ | $10\sigma(i)$ | 1.5 | 1
TRi,d | $10^{\zeta(\textrm{TR}_{\cdot,d})}\sigma_{max}$ | $10\sigma(i)$ | 1.5 | 1
Clause | CLℓ | $10^{\zeta(\textrm{CL}_{\cdot})}\sigma_{max}$ | $10\sigma(\ell)$ | 2 | 1
Dummy | DM | $10^{\zeta(\textrm{DM})}\sigma_{max}$ | 0 | 1 | 2
Link $h\in\\{0,1,\cdots,2\gamma+2\\}$ | LNi,h,+ | $10^{\zeta(\textrm{LN}_{\cdot,+})}\sigma_{max}$ | $10{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | 1 | 2
LNi,h,- | $10^{\zeta(\textrm{LN}_{\cdot,-})}\sigma_{max}$ | $10{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | 1 | 2
Variable-Link | $\theta_{\textrm{V-L},i,+}$ | $(10^{14}-10^{\zeta(\textrm{LN}_{\cdot,+})}-10^{\zeta(V_{\cdot,+,2})})\sigma_{max}$ | $-10({\mathchoice{\mbox{\boldmath$\displaystyle\bf a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{1}_{i}){\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | -3
$\theta_{\textrm{V-L},i,-}$ | $(10^{14}-10^{\zeta(\textrm{LN}_{\cdot,-})}-10^{\zeta(V_{\cdot,-,2})})\sigma_{max}$ | $-10({\mathchoice{\mbox{\boldmath$\displaystyle\bf a$}}{\mbox{\boldmath$\textstyle\bf a$}}{\mbox{\boldmath$\scriptstyle\bf a$}}{\mbox{\boldmath$\scriptscriptstyle\bf a$}}}_{i}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{1}_{i}){\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | -3
Link-Link $h\in\\{1,\cdots,2\gamma+1\\}$ | $\theta_{\textrm{L-L},i,h,+}$ | $(10^{14}-2\times 10^{\zeta(\textrm{LN}_{\cdot,+})})\sigma_{max}$ | $-10({\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h+1}_{i}){\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | -3
$\theta_{\textrm{L-L},i,h,-}$ | $(10^{14}-2\times 10^{\zeta(\textrm{LN}_{\cdot,-})})\sigma_{max}$ | $-10({\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}+\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}}^{h+1}_{i}){\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | -3
$\theta_{\textrm{L-L},i,+,-}$ | $(10^{14}-10^{\zeta(\textrm{LN}_{\cdot,+})}-10^{\zeta(\textrm{LN}_{\cdot,-})})\sigma_{max}$ | $-20{\mathchoice{\mbox{\boldmath$\displaystyle\bf b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{2\gamma+2}_{i}{\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$ | -3
Variable-Clause -Dummy, $|i-\ell|\leq 1$ | $\theta_{\textrm{V-C-D},\ell,i,+}$ | $(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(\textrm{CL}_{\cdot})}-10^{\zeta(V_{\cdot,+,1})})\sigma_{max}$ | $-10(\sigma(\ell)+\sigma(i))$ | -4
$\theta_{\textrm{V-C-D},\ell,i,-}$ | $(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(\textrm{CL}_{\cdot})}-10^{\zeta(V_{\cdot,-,1})})\sigma_{max}$ | $-10(\sigma(\ell)+\sigma(i))$ | -4
Variable-Dummy | $\theta_{\textrm{V-D},i,+}$ | $(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(V_{\cdot,+,1})})\sigma_{max}$ | $-10\sigma(i)$ | -3
$\theta_{\textrm{V-D},i,-}$ | $(10^{14}-10^{\zeta(\textrm{DM})}-10^{\zeta(V_{\cdot,-,1})})\sigma_{max}$ | $-10\sigma(i)$ | -3
Variable-Truth | $\theta_{\textrm{V-T},i,a,c}$ | $(10^{14}-10^{\zeta(V_{\cdot,+,1})}-10^{\zeta(\textrm{TR}_{\cdot,a})}-10^{\zeta(\textrm{TR}_{\cdot,c})})\sigma_{max}$ | $-30\sigma(i)$ | -4
$\theta_{\textrm{V-T},i,b,d}$ | $(10^{14}-10^{\zeta(V_{\cdot,+,2})}-10^{\zeta(\textrm{TR}_{\cdot,b})}-10^{\zeta(\textrm{TR}_{\cdot,d})})\sigma_{max}$ | $-30\sigma(i)$ | -4
$\theta_{\textrm{V-T},i,a,d}$ | $(10^{14}-10^{\zeta(V_{\cdot,-,1})}-10^{\zeta(\textrm{TR}_{\cdot,a})}-10^{\zeta(\textrm{TR}_{\cdot,d})})\sigma_{max}$ | $-30\sigma(i)$ | -4
$\theta_{\textrm{V-T},i,b,c}$ | $(10^{14}-10^{\zeta(V_{\cdot,-,2})}-10^{\zeta(\textrm{TR}_{\cdot,b})}-10^{\zeta(\textrm{TR}_{\cdot,c})})\sigma_{max}$ | $-30\sigma(i)$ | -4

Table 2: Job processing times

##  Appendix G Proof of Theorem 2

The proof is carried out in 4 steps. We first show in Section G.1 that every
job in the constructed instance has a unique processing time. This allows us
to refer to a job by its symbol (e.g., $V_{i,+,1}^{T}$) as well as by its
processing time. Next, we show in Section G.2 that if a significant fraction
of clauses in the 3SAT′ instance are satisfiable, then the constructed
scheduling instance admits a solution with a small objective value. Next, we
show in Section G.3 that if any truth-assignment for the 3SAT′ instance will
leave a significant fraction of clauses unsatisfied, then the constructed
scheduling instance does not admit a solution with a small objective value.
Finally, we are able to prove the correctness of our reduction in Section G.4
by leveraging the above two facts.

###  G.1 Uniqueness of job processing times

We claim that the processing time of each job we create is unique, whereas
there is a one-to-one correspondence between the symbol of a job and its
processing time. To see the claim, consider Table 2. It suffices to compare
the processing time of jobs within each subtype. Given that $\sigma$ is an
injection, it is easy to see that the processing time of each variable job,
truth-assignment job, clause job, variable-dummy job and variable-truth job is
unique. For variable-clause-dummy jobs, by property 4 of Lemma 6 we know the
sum $\sigma(\ell)+\sigma(i)$ for $i=\ell-1,\ell,\ell+1$ is unique. The
uniqueness of link jobs follows from the uniqueness of
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h}_{i}$’s from Lemma 9. The
uniqueness of link-link jobs follows from the uniqueness of the summation
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf
b$}}}^{h}_{i}+{\mathchoice{\mbox{\boldmath$\displaystyle\bf
b$}}{\mbox{\boldmath$\textstyle\bf b$}}{\mbox{\boldmath$\scriptstyle\bf
b$}}{\mbox{\boldmath$\scriptscriptstyle\bf b$}}}^{h+1}_{i}$ from Lemma 10.

###  G.2 3SAT′ to Scheduling

The goal of this subsection is to prove the following lemma.

######  Lemma 22.

If there are at most $\vartheta n$ clauses which are not satisfied, then the
constructed scheduling instance admits a feasible schedule with objective
value at most $(10^{14}\sigma_{max})^{q}(2\gamma n+8n)+\vartheta
n\cdot\frac{q(q-1)}{2}(10^{14}\sigma_{max})^{q-2}+o(n\sigma_{max}^{q-2})$.

Recall that every main job, except the clause job, admits a true copy and
false copy, while the clause job admits a true copy and two false copies. We
first ignore the true/false version of jobs and schedule them according to
Table 3, where each row represents jobs that are scheduled on one machine.

Variable-Link | $\theta_{\textrm{V-L},i,+}$ | $V_{i,+,2}$ | LNi,1,+ | $\backslash$
---|---|---|---|---
$\theta_{\textrm{V-L},i,-}$ | $V_{i,-,2}$ | LNi,1,- | $\backslash$
Link-Link $h\in\\{1,2,\cdots,2\gamma+1\\}$ | $\theta_{\textrm{L-L},i,h,+}$ | LNi,h,+ | LNi,h+1,+ | $\backslash$
$\theta_{\textrm{L-L},i,h,-}$ | LNi,h,- | LNi,h+1,- | $\backslash$
$\theta_{\textrm{L-L},i,+,-}$ | LNi,2γ+2,+ | LNτ(i),2γ+2,- | $\backslash$
Variable-Clause-Dummy $|i-\ell|\leq 1$ | $\theta_{\textrm{V-C-D},\ell,i,+}$ | $V_{i,+,1}$ | CLℓ | DM
$\theta_{\textrm{V-C-D},\ell,i,-}$ | $V_{i,-,1}$ | CLℓ | DM
Variable-Dummy | $\theta_{\textrm{V-D},i,+}$ | $V_{i,+,1}$ | DM | $\backslash$
$\theta_{\textrm{V-D},i,-}$ | $V_{i,-,1}$ | DM | $\backslash$
Variable-Truth | $\theta_{\textrm{V-T},i,a,c}$ | $V_{i,+,1}$ | TRi,a | TRi,c
$\theta_{\textrm{V-T},i,b,d}$ | $V_{i,+,2}$ | TRi,b | TRi,d
$\theta_{\textrm{V-T},i,a,d}$ | $V_{i,-,1}$ | TRi,a | TRi,d
$\theta_{\textrm{V-T},i,b,c}$ | $V_{i,-,2}$ | TRi,b | TRi,c

Table 3: SAT to Scheduling – Jobs scheduled on each machine

We show that if we schedule according to Table 3, then every job has been
scheduled (ignoring the superscripts $T$ or $F$, which will be determined
later). It is obvious that every gap job is scheduled. For simplicity, we
abuse the notation a bit by using the symbol of a gap job to denote the
machine on which it is scheduled.

$\bullet$ Consider clause jobs. Recall that for each clause $cl_{\ell}$ and
$i=\ell-1,\ell,\ell+1$, we either construct $\theta_{\textrm{V-D},i,-}$ and
$\theta_{\textrm{V-C-D},\ell,i,+}$ if the positive literal $z_{i}$ occurs in
$C_{1}$, or construct $\theta_{\textrm{V-D},i,+}$ and
$\theta_{\textrm{V-C-D},\ell,i,-}$ if the negative literal $\neg z_{i}$ occurs
in $C_{1}$. Hence the three copies of job $\textrm{CL}_{\ell}$ appear on
machine $\theta_{\textrm{V-C-D},\ell,\ell-1,+}$ or
$\theta_{\textrm{V-C-D},\ell,\ell-1,-}$, machine
$\theta_{\textrm{V-C-D},\ell,\ell,+}$ or
$\theta_{\textrm{V-C-D},\ell,\ell,-}$, and machine
$\theta_{\textrm{V-C-D},\ell,\ell+1,+}$ or
$\theta_{\textrm{V-C-D},\ell,\ell+1,-}$. Thus, all three copies of a clause
job are scheduled.

$\bullet$ Consider truth-assignment jobs. There are two copies of TRi,a,
TRi,b, TRi,c and TRi,d. It is easy to see that all of them are scheduled on
machines $\theta_{\textrm{V-T},i,a,c}$, $\theta_{\textrm{V-T},i,b,d}$,
$\theta_{\textrm{V-T},i,a,d}$ and $\theta_{\textrm{V-T},i,b,c}$.

$\bullet$ Consider variable jobs. There are two copies of $V_{i,+,1}$,
$V_{i,+,2}$, $V_{i,-,1}$ and $V_{i,-,2}$. It is easy to see that one copy of
them are scheduled on machines $\theta_{\textrm{V-T},i,a,c}$,
$\theta_{\textrm{V-T},i,b,d}$, $\theta_{\textrm{V-T},i,a,d}$ and
$\theta_{\textrm{V-T},i,b,c}$. One copy of $V_{i,+,2}$ and $V_{i,-,2}$ are
scheduled on machines $\theta_{\textrm{V-L},i,+}$ and
$\theta_{\textrm{V-L},i,-}$. If machines $\theta_{\textrm{V-D},i,-}$ and
$\theta_{\textrm{V-C-D},\ell,i,+}$ exist (when the positive literal $z_{i}$
occurs in $C_{1}$), then $V_{i,-,1}$ and $V_{i,+,1}$ are scheduled on them
respectively; otherwise machines $\theta_{\textrm{V-D},i,+}$ and
$\theta_{\textrm{V-C-D},\ell,i,-}$ exist (the negative literal $\neg z_{i}$
occurs in $C_{1}$), then $V_{i,+,1}$ and $V_{i,-,1}$ are scheduled on them
respectively.

$\bullet$ Consider link jobs. There are two copies of LNi,h,+ (or LNi,h,-) for
$1\leq h\leq 2\gamma+2$. Let $\iota\in\\{+,-\\}$. The two copies of LNi,1,ι
are scheduled on machines $\theta_{\textrm{V-L},i,\iota}$ and
$\theta_{\textrm{L-L},i,1,\iota}$. The two copies of LNi,h,ι are scheduled on
$\theta_{\textrm{L-L},i,h,\iota}$ and $\theta_{\textrm{L-L},i,h+1,\iota}$ for
$2\leq h\leq 2\gamma+1$. The two copies of LNi,2γ+2,+ are scheduled on
machines $\theta_{\textrm{L-L},2\gamma+1,+}$ and
$\theta_{\textrm{L-L},i,+,-}$, and the two copies of LNi,2γ+2,- are scheduled
on machines $\theta_{\textrm{L-L},2\gamma+1,-}$ and
$\theta_{\textrm{L-L},\tau^{-1}(i),+,-}$, where $\tau^{-1}$ is the inverse of
the mapping $\tau$ (note that $\tau^{-1}$ exists since $\tau$ is one-to-one).

$\bullet$ Consider dummy jobs. There are in total $2n$ dummy jobs. It is
obvious that for every $i$, 2 dummy jobs are scheduled on machines
$\theta_{\textrm{V-C-D},\ell,i,+}$, $\theta_{\textrm{V-D},i,-}$ or machines
$\theta_{\textrm{V-C-D},\ell,i,-}$, $\theta_{\textrm{V-D},i,+}$.

Next, we consider the load of every machine. According to Table 2, it is easy
to verify that if we sum up the type-component of jobs on each machine, it
becomes $10^{14}\sigma_{max}$; if we sum up the index-component of jobs on
each machine, it becomes $0$. Now we consider the T/F-component of jobs. It is
easy to verify that the T/F-components of all jobs add up to $0$, hence we
have the following direct observation.

######  Observation 5.

The total processing time of all jobs add up to
$10^{14}\sigma_{max}\cdot(2\gamma n+8n)$.

Variable-Link | $\theta_{\textrm{V-L},i,+}$ | $V_{i,+,2}^{T}$ | LN${}_{i,1,+}^{F}$ | $\backslash$
---|---|---|---|---
$\theta_{\textrm{V-L},i,-}$ | $V_{i,-,2}^{F}$ | LN${}_{i,1,-}^{T}$ | $\backslash$
Link-Link $h\in\\{1,2,\cdots,2\gamma+1\\}$ | $\theta_{\textrm{L-L},i,h,+}$ | LN${}_{i,h,+}^{F}$ | LN${}_{i,h+1,+}^{T}$ | $\backslash$
$\theta_{\textrm{L-L},i,h,-}$ | LN${}_{i,h,-}^{F}$ | LN${}_{i,h+1,-}^{T}$ | $\backslash$
$\theta_{\textrm{L-L},i,+,-}$ | LN${}_{i,2\gamma+2,+}^{T}$ | LN${}_{\tau(i),2\gamma+2,-}^{*}$ | $\backslash$
Variable-Clause-Dummy & Variable-Dummy Case 1: positive literal $z_{i}\in C_{1}$ | $\theta_{\textrm{V-C-D},\ell,i,+}$ | $V_{i,+,1}^{T}$ | CL${}_{\ell}^{*}$ | DM∗
$\theta_{\textrm{V-D},i,-}$ | $V_{i,-,1}^{F}$ | DM∗ | $\backslash$
Variable-Clause-Dummy & Variable-Dummy Case 2: negative literal $\neg z_{i}\in C_{1}$ | $\theta_{\textrm{V-C-D},i,-}$ | $V_{i,-,1}^{F}$ | CL${}_{\ell}^{*}$ | DM∗
$\theta_{\textrm{V-D},i,+}$ | $V_{i,+,1}^{T}$ | DM∗ | $\backslash$
Variable-Truth | $\theta_{\textrm{V-T},i,a,c}$ | $V_{i,+,1}^{F}$ | TR${}_{i,a}^{F}$ | TR${}_{i,c}^{F}$
$\theta_{\textrm{V-T},i,b,d}$ | $V_{i,+,2}^{F}$ | TR${}_{i,b}^{F}$ | TR${}_{i,d}^{F}$
$\theta_{\textrm{V-T},i,a,d}$ | $V_{i,-,1}^{T}$ | TR${}_{i,a}^{T}$ | TR${}_{i,d}^{T}$
$\theta_{\textrm{V-T},i,b,c}$ | $V_{i,-,2}^{T}$ | TR${}_{i,b}^{T}$ | TR${}_{i,c}^{T}$

Table 4: Scheduling of Truth/False types of jobs if the variable $z_{i}$ is
true

Variable-Link | $\theta_{\textrm{V-L},i,+}$ | $V_{i,+,2}^{F}$ | LN${}_{i,1,+}^{T}$ | $\backslash$
---|---|---|---|---
$\theta_{\textrm{V-L},i,-}$ | $V_{i,-,2}^{T}$ | LN${}_{i,1,-}^{F}$ | $\backslash$
Link-Link $h\in\\{1,2,\cdots,2\gamma+1\\}$ | $\theta_{\textrm{L-L},i,h,+}$ | LN${}_{i,h,+}^{T}$ | LN${}_{i,h+1,+}^{F}$ | $\backslash$
$\theta_{\textrm{L-L},i,h,-}$ | LN${}_{i,h,-}^{T}$ | LN${}_{i,h+1,-}^{F}$ | $\backslash$
$\theta_{\textrm{L-L},i,+,-}$ | LN${}_{i,2\gamma+2,+}^{F}$ | LN${}_{\tau(i),2\gamma+2,-}^{*}$ | $\backslash$
Variable-Clause-Dummy & Variable-Dummy Case 1: positive literal $z_{i}\in C_{1}$ | $\theta_{\textrm{V-C-D},\ell,i,+}$ | $V_{i,+,1}^{F}$ | CL${}_{\ell}^{*}$ | DM∗
$\theta_{\textrm{V-D},i,-}$ | $V_{i,-,1}^{T}$ | DM∗ | $\backslash$
Variable-Clause-Dummy & Variable-Dummy Case 2: negative literal $\neg z_{i}\in C_{1}$ | $\theta_{\textrm{V-C-D},i,-}$ | $V_{i,-,1}^{T}$ | CL${}_{\ell}^{*}$ | DM∗
$\theta_{\textrm{V-D},i,+}$ | $V_{i,+,1}^{F}$ | DM∗ | $\backslash$
Variable-Truth | $\theta_{\textrm{V-T},i,a,c}$ | $V_{i,+,1}^{T}$ | TR${}_{i,a}^{T}$ | TR${}_{i,c}^{T}$
$\theta_{\textrm{V-T},i,b,d}$ | $V_{i,+,2}^{T}$ | TR${}_{i,b}^{T}$ | TR${}_{i,d}^{T}$
$\theta_{\textrm{V-T},i,a,d}$ | $V_{i,-,1}^{F}$ | TR${}_{i,a}^{F}$ | TR${}_{i,d}^{F}$
$\theta_{\textrm{V-T},i,b,c}$ | $V_{i,-,2}^{F}$ | TR${}_{i,b}^{F}$ | TR${}_{i,c}^{F}$

Table 5: Scheduling of Truth/False types of jobs if the variable $z_{i}$ is
false

Consider the truth-assignment of $I_{sat}$. If the variable $z_{i}$ is true,
then we determine the true/false version of main jobs according to Table 4.
Otherwise the variable $z_{i}$ is false in the assignment, then we flip the
True/False version of all jobs in Table 4, i.e., we schedule according to
Table 5. It is easy to see that in each row of Table 4, if there is no job
with a superscript of $*$, then their T/F-components sum up to $0$, i.e., the
load of this machine is exactly $10^{14}\sigma_{max}$. We call the current
schedule a semi-schedule. It remains to determine the true/false version of
jobs with the superscript $*$.

$\bullet$ Consider link-link machines. We only need to consider machines
$\theta_{\textrm{L-L},i,+,-}$. The T/F-type of the job LNi,2γ+2,+ has already
been decided based on the true/false of variable $z_{i}$. Consider the other
job LNτ(i),2γ+2,- scheduled on this machine. Notice that based on the
true/false of the variable $z_{\tau(i)}$, one copy of LNτ(i),2γ+2,- is
scheduled on $\theta_{\textrm{L-L},\tau(i),2\gamma+1,-}$, and the remaining
copy is scheduled on $\theta_{\textrm{L-L},i,+,-}$. If $z_{\tau(i)}$ is true,
the remaining copy is LN${}_{\tau(i),2\gamma+2,-}^{F}$; otherwise, the
remaining copy is LN${}_{\tau(i),2\gamma+2,-}^{T}$. Hence, we have the
following observation:

  * –

if variables $z_{i}$ is true and $z_{\tau(i)}$ is false, then
LN${}_{i,2\gamma+2,+}^{T}$ and LN${}_{\tau(i),2\gamma+2,-}^{T}$ are on this
machine, whereas the load is $10^{14}\sigma_{max}-1$;

  * –

if variables $z_{i}$ is false and $z_{\tau(i)}$ is true, then
LN${}_{i,2\gamma+2,+}^{F}$ and LN${}_{\tau(i),2\gamma+2,-}^{F}$ are on this
machine, whereas the load is $10^{14}\sigma_{max}+1$;

  * –

if variables $z_{i}$ and $z_{\tau(i)}$ are both true or both false, then one
of LNi,2γ+2,+ and LNτ(i),2γ+2,- is true and the other is false, whereas the
load is $10^{14}\sigma_{max}$.

The above observation leads to the following claim.

######  Claim 2.

The load of machine $\theta_{\textrm{L-L},i,+,-}$ is $10^{14}\sigma_{max}$ if
the clause $(z_{i}\oplus\neg z_{\tau(i)})$ is satisfied, and is
$10^{14}\sigma_{max}\pm 1$ otherwise.

$\bullet$ Consider variable-clause-dummy and variable-dummy machines. Notice
that there is one true copy and two false copies of CLℓ, scheduled on machines
$\theta_{\textrm{V-C-D},\ell,i,\kappa_{i-\ell}}$ where
$i\in\\{\ell-1,\ell,\ell+1\\}$ and $\kappa_{i-\ell}\in\\{+,-\\}$. If there
exists at least one $i=i^{*}$ such that $V_{i,\kappa_{i^{*}-\ell},1}^{T}$ is
on machine $\theta_{\textrm{V-C-D},\ell,i^{*},\kappa_{i^{*}-\ell}}$, then we
schedule CL${}_{\ell}^{T}$ on machine
$\theta_{\textrm{V-C-D},\ell,i^{*},\kappa_{i^{*}-\ell}}$, and schedule the two
copies of CL${}_{\ell}^{F}$ on the remaining two machines, respectively.
Otherwise, we schedule CL${}_{\ell}^{T}$ on machine
$\theta_{\textrm{V-C-D},\ell,\ell-1,\kappa_{-1}}$ and the two false copies
CL${}_{\ell}^{F}$ on machines $\theta_{\textrm{V-C-D},\ell,i,\kappa_{i-\ell}}$
where $i=\ell,\ell+1$.

Finally, we determine the true/false version of dummy jobs on variable-clause-
dummy and variable-dummy machines. Recall that there are $n+n/3$ true dummy
and $n-n/3$ false dummy jobs.

On variable-clause-dummy machines, if the clause job is true, schedule a true
dummy job. Otherwise, the clause job is false, then if the variable job is
true (or false), schedule a false (or true) dummy job.

On variable-dummy machines, we schedule dummy jobs in the following way. A
false variable job is always scheduled with a true dummy job. For true
variable jobs, we first partition the indices of variables,
$\\{1,2,\cdots,n\\}$, into two subsets $S_{1},S_{2}$ such that

$S_{1}=\\{i:{\textrm{On machine
$\theta_{\textrm{V-C-D},\ell,i,\kappa_{i-\ell}}$ there is a true clause job
and a false variable job}}\\},$

and $S_{2}$ consists of the remaining indices. On machine
$\theta_{\textrm{V-D},i,+}$ or $\theta_{\textrm{V-D},i,-}$ where $i\in S_{1}$
and the variable job is true, we schedule a true dummy job; on machine
$\theta_{\textrm{V-D},i,+}$ or $\theta_{\textrm{V-D},i,-}$ where $i\not\in