\section{Introduction}

We consider fixed-priority uniprocessor real-time task scheduling with constrained deadlines and arbitrary release jitter in the \emph{sporadic task model} \cite{DBLP:phd/ndltd/Mok83} which is a common model to analyze real-time task systems. 





\subparagraph*{Model}

A sporadic task system $\mathscr{T}=\set{\tau_1,\dots,\tau_n}$ is a set of sporadic tasks $
\tau_i$ which are given as a quadruple of non-negative integers $\tau_i = (c_i,d_i,p_i,\jitter_i)$ where $c_i$ represents the task's worst-case execution time, $d_i$ its relative deadline, $p_i$ its period, and $\jitter_i$ its release jitter. The task $\tau_i$ generates an infinite sequence of jobs. Each job has an execution time of at most $c_i \geq 1$ time units and a deadline exactly $d_i$ time units after its arrival time, where $c_i \leq d_i \leq p_i$. The jobs of the task are considered to arrive separated in time by at least $p_i\geq 1$ time units. However, a job is not ready for execution until it is \emph{released}. The time difference between the arrival time and the release time is called \emph{release jitter}. Hence,
in jitter-free systems the jobs are released in the moment they arrive, i.e.
arrival time equals release time.
The release jitter $\jitter_i$ of the task is the maximum time difference between the arrival times and the release times over all jobs of $\tau_i$.

The task system $\mathscr{T}$ has \emph{harmonic periods} iff $p_i \geq p_j$ implies that $p_i/p_j\in\Z$ for all tasks $\tau_i,\tau_j$.
The \emph{utilization} of a task $\tau_i$ is the quantity $c_i/p_i$ and the utilization of the task set $\mathscr{T}$ is $\sum_{i\leq n}c_i/p_i$. The common assumption is that $\sum_{i\leq n}c_i/p_i \leq 1$ as otherwise there are job sequences of $\mathscr{T}$ which can not be scheduled by any algorithm. We refer to this utilization bound as the \emph{schedulability utilization bound}. However, a necessary utilization bound is $\sum_{i<n}c_i/p_i < 1$ as otherwise there is no solution for worst-case response times at all. We refer to this bound as the \emph{general utilization bound}.

\begin{figure}[h]
    \centering
    \tikz[xscale=0.19,yscale=0.6]{
        \def.15{.15}
        \def.2{.2}
        \foreach [count=\i] \c/\p/\jit/\periods/\ops in {
            15/65/8/1/[fill=white!50!blue],
            7/30/5/2/[fill=orange],
            13/50/25/1/[fill=white]
        } {
           
            \draw [gray] (0,-\i) node [left=5,black] {$\tau_{\i}$} -- (65,-\i);
            \foreach \j in {1,...,\periods} {
                \def\ifnum\j>1{\j}\else{}\fi{\ifnum\j>1{\j}\else{}\fi}
                \draw (\j*\p,-\i+.2) -- (\j*\p,-\i-.2) node [below] {$\ifnum\j>1{\j}\else{}\fi p_{\i}$};
                \draw [-stealth] (\j*\p-\p+\jit,-\i-4*.15) -- (\j*\p-\p+\jit,-\i-.15);
                \draw \ops (\j*\p-\p+\jit,-\i-.15) rectangle (\j*\p-\p+\jit+\c,-\i+.15);
            }
        }
        \draw (0,-1+.2) -- (0,-4-.2) node [below] {$0$};
        \draw [gray] (0,-4) node [left=5,black] {\textsc{fp}} -- (65,-4);
        \draw [fill=orange] (5,-4-.15) rectangle (8,-4+.15);
        \draw [fill=white!50!blue] (8,-4-.15) rectangle (23,-4+.15);
        \draw [fill=orange] (23,-4-.15) rectangle (27,-4+.15);
        \draw [fill=white] (27,-4-.15) rectangle (35,-4+.15);
        \draw [fill=orange] (35,-4-.15) rectangle (42,-4+.15);
        \draw [fill=white] (42,-4-.15) rectangle (47,-4+.15);
    }
    \caption{An example instance $\mathscr{T} = \set{\tau_1,\tau_2,\tau_3}$ with $\tau_1 = (15,d_1,65,8)$, $\tau_2 = (7,d_2,30,5)$, $\tau_3 = (13,d_3,50,25)$ and the resulting \acs{FP} schedule. The arrows indicate the release times of the jobs.}
    \label{fig:example}
\end{figure}

\subparagraph*{Fixed-priority scheduling}

In \ac{FP} scheduling (or static-priority scheduling) the tasks are considered to have a predefined order of priorization. A task $\tau_i$ has a larger priority than a task $\tau_j$ if and only if $i<j$. An \ac{FP} schedule preempts jobs according to these priorities; in more detail, a running job is preempted on the release of a job of task of a higher priority to schedule the new job instead (see \cref{fig:example} for an example).

Two important special cases of \ac{FP} scheduling are \ac{DM} scheduling \cite{DBLP:journals/rts/Baruah11,AUDSLEY1991127} and \ac{RM} scheduling \cite{DBLP:conf/rtss/Ekberg20,DBLP:journals/jacm/LiuL73,DBLP:conf/afips/Serlin72}.
In \ac{DM} scheduling earlier deadlines imply larger priorities while in \ac{RM} scheduling smaller periods imply larger priorities. Both are equal if the deadline of each task is equal to its period.

\subparagraph*{Response time analysis and schedulability testing}

The \emph{response time} of a task is the maximum time difference between the arrival of a job and its completion. In a worst-case scenario we refer to them as \emph{worst-case response times} and these may be used to decide the schedulability of a system. Since task release jitters intensify the complexity of worst-case response times and schedulability testing as well as other types of analysis, they are often assumed to be zero, i.e. $\jitter_i=0$ for all $i\leq n$.
As pointed out by Liu and Layland \cite{DBLP:journals/jacm/LiuL73}, in such \emph{jitter-free} systems the \emph{critical instant} occurs when the jobs of all tasks $\tau_i$ are released simultaneously.
Therefore, without release jitters the worst-case response time of task $\tau_j$ is the earliest point in time $r_j$ where
\[
    \textstyle
    r_j \geq c_j + \sum_{i=1}^{j-1}c_i\ceil{r_j/p_i}.
\]
This inequality models the situation that all jobs are released at time $0$.
If $r_j \leq d_j$, then task $t_j$ completes its job on time which means that task $\tau_j$ is schedulable. If $r_j \leq d_j$ for all tasks $t_j$, then the task system $\mathscr{T}$ is schedulable using the given priorities.


In this paper we consider systems with release jitters. Audsley et al. \cite{DBLP:journals/iee/AudsleyBRTW93} and Tindell et al. \cite{DBLP:journals/rts/TindellBW94} have discussed the release jitter problem in detail. Their work leads to the following understanding of worst-case response times in systems with task release jitters.
The worst-case response time of task $\tau_j$ is the earliest point in time $r_j$ where
\[
    \textstyle
    r_j \geq c_j + \sum_{i=1}^{j-1}c_i\ceil{(r_j+\jitter_i)/p_i}.
\]
The task is schedulable if $r_j \leq d_j-\jitter_j$ and the task set $\mathscr{T}$ is schedulable if $r_j \leq d_j-\jitter_j$ for all tasks $\tau_j$.
Without loss of generality we can assume that the execution requirement of each job of a task $\tau_i$ always equals the task's worst-case execution time $c_i$. Also we can assume that the $i$-th job of a task $\tau_j$ is released at time $(i-1)p_j+\jitter_j$ and its due time is $(i-1)p_j+d_j$. See also \ac{SAS} \cite{DBLP:reference/crc/BaruahG04,DBLP:journals/cj/JosephP86,DBLP:journals/rts/TindellBW94}.
Furthermore, we may restrict our interest to the response time $r_n$ of the last task $\tau_n$:
\[\addtocounter{equation}{1}\tag{\theequation}\label{wcrt-with-jitters-original}
    r_n = \min\set{t|t \geq c_n + \sum_{i<n} c_i\ceil[\Big]{\frac{t+\jitter_i}{p_i}}, t \in \Z_{\geq 0}}.
\]
We refer to the problem to compute $r_n$ as \emph{response time computation} (RTC).

For \ac{FP} scheduling, RTC is NP-hard in general due to Eisenbrand and Rothvoß \cite{DBLP:conf/rtss/EisenbrandR08} even for $\jitter=0$ and it is even hard to approximate within a constant factor. However, for harmonic periods it is polynomial which is a great result by Bonifaci~et~al.~\cite{DBLP:conf/rtss/BonifaciMMW13} and it may even be computed in near-linear time, cf. Nguyen~et~al.~\cite{DBLP:conf/iwoca/NguyenGJ22}.

The computation of response times in real-time systems is often treated as a fixed point problem, where one aims for the smallest fixed point $t$ to the fixed point equation
\(\Phi(t) = t\)
where $\Phi(t) = c_n+\sum_{i<n}c_i\ceil{(t+\jitter_i)/p_i}$. Especially, this allows to argue about intersections of $\Phi$ with the identity function. However, in this paper we present a whole new approach.

\subparagraph*{Mixing Set}

In the \textsc{Mixing Set} problem one is given capacities $a\in\Q^n$ and a right-hand side $b\in\Q^n$ and the goal is to find a solution $(s,x)\in\R_{\geq 0}\times\Z^n$ which optimizes a linear objective function while satisfying the following system of inequalities:
\begin{align*}
    s+a_ix_i & \geq b_i \quad \forall i\in\set{1,\dots,n}
\end{align*}
The problem is \NP-hard due to Eisenbrand and Rothvoß \cite{DBLP:conf/approx/EisenbrandR09}. However, it can be solved in polynomial time in the case of unit capacities \cite{DBLP:journals/mp/GunlukP01,DBLP:journals/mp/MillerW03} or harmonic capacities \cite{DBLP:journals/mp/ZhaoF08} (see also \cite{DBLP:conf/ipco/ConfortiSW08,DBLP:journals/orl/ConfortiZ09} for simpler approaches). The \textsc{Mixing Set} problem plays an important role in production planning (in particular lot-sizing \cite{Pochet:2006:PPM:1202598}).

\subparagraph*{Related work}

In the early '70s it was independently shown by Liu and Layland \cite{DBLP:journals/jacm/LiuL73} and Serlin \cite{DBLP:conf/afips/Serlin72}, that a set of $n$ implicit-deadline synchronous periodic tasks is always schedulable in \ac{RM} scheduling if the task's total utilization is bounded by $n(2^{1/n}-1)$ which is $\ln(2)\approx 0.69$ for $n\rightarrow\infty$. Recently, this seminal result was complemented by Ekberg \cite{DBLP:conf/rtss/Ekberg20} who proved that $\ln(2)$ is in fact the boundary between polynomial and NP-hard schedulability testing; the \ac{FP} schedulability problem is NP-hard even if it is restricted to task sets with \ac{RM} priorities and utilization-bounded from above by any constant truly larger than $\ln(2)$.

Baruah \cite{DBLP:conf/rtss/Baruah20} introduced the idea of ILP-tractability of schedulability analysis problems and in fact, our results prove tractability in his sense.
As mentioned earlier, Eisenbrand and Rothvoß proved hardness results for both RTC \cite{DBLP:conf/rtss/EisenbrandR08} and the \textsc{Mixing Set} problem \cite{DBLP:conf/approx/EisenbrandR09}; in fact, they proved reductions from directed diophantine approximation \emph{to} these problems but they did not give any reductions from them or \emph{between} them, which is what we have found.

\begin{table}[H]
    \centering
    \begin{tabularx}{\textwidth}{p{3cm}|p{5.5cm}|X}
        \toprule
            \textsc{RTC} & $p_i$ harmonic & $p_i \geq 1$
        \\\hline
            $\jitter_i \leq p_i$
            &
            $\Oh(n^2(q+\log p_{\max}))$ *
            &
            $\Oh(n\lcm_{i<n}p_i)$ *\newline
            $\Oh(\max(Sn,T_{\mixing}\log p_{\max}))$ *
        \\\hline
       
       
       
       
       
       
            $\jitter_i=0$
            &
            $\Oh(n\log(n+p_{\max}))$ \cite{DBLP:conf/rtss/BonifaciMMW13}, $\Oh(n\log n)$ \cite{DBLP:conf/iwoca/NguyenGJ22}
            &
            $\Oh(T_{\mixing}\log p_{\max})$ *
        \\\midrule
            \textsc{Mixing Set} & $a_i$ harmonic & $a_i \geq 1 $
        \\\hline
            $b_i \in \Z$
            &
            $\Oh(n^2)$ \cite{DBLP:journals/orl/ConfortiZ09}
            &
            $\Oh(n\lcm_{i\leq n}a_i)$ *\newline
            $\Oh(T_{\response}\log b_{\max})$ *
        \\\hline
       
       
       
       
       
            $b_i = \beta \geq \lcm_{j\leq n} a_j$
            &
            $\Oh(n\log(n+\beta))$ *
            &
            $\Oh(T_{\response}\log\beta)$ *
       
       
        \\\bottomrule
    \end{tabularx}
    \medskip
    \caption{Overview of algorithmic results for RTC and \textsc{Mixing Set}. Here $S \leq (\sum_{i<n}c_i)/(1-U)$ for utilization $U=\sum_{i<n}c_i/p_i$ is an upper bound on the value of $s$ in any optimal solution to an instance of \textsc{Mixing Set}, $T_{\mixing}$ and $T_{\response}$ are upper bounds on the time required to solve an instance of \textsc{Mixing Set} or RTC, respectively, and $q \leq \abs{\set{p_i-\jitter_i|i\leq n}} \leq n$.\hfill * Result is in this paper}
    \label{tab:results-overview}
\end{table}

\subparagraph*{Our contribution}
Here we give a short summary about all of our results.
\begin{enumerate}[(a)]
    \item\label{dualision-teaser}
   
    We present a simple dualization technique which allows to solve inequality-constrained optimization problems in a binary search by consecutively solving a dual formulation of the associated decision problem (see \cref{dualision}).
    \item \para{Response Times}
    \begin{enumerate}[1.]
        \item We establish new bounds for worst-case response times in \ac{FP} real-time task systems with period-constrained task release jitter (see \cref{sec:response-time-bounds}).
        \item We present a conditional Karp reduction from RTC to the \textsc{Mixing Set} problem (see \cref{conditional-karp-reduction}). We show how it can be used to derive a bunch of algorithmic results for both problems (see \cref{tab:results-overview} for an overview).
        \item For the most important case of harmonic periods we prove a Cook reduction from RTC to \textsc{Mixing Set} (see \cref{wcrt-harmonic-periods}).
        \item Usually, algorithmic results for worst-case response times are achieved for special cases like equal or harmonic periods only; in fact, we can cope even with the general case of \emph{arbitrary} periods. Especially, we give a Turing reduction from RTC to \textsc{Mixing Set} and we study the dependence of the running times on the utilization (see \cref{wcrt-arbitrary-periods}).
    \end{enumerate}
    \item \para{Mixing Set} We can reverse our methodology to solve the \textsc{Mixing Set} problem by computing worst-case response times for associated real-time task systems (see \cref{sec:mixing-set}).
    \item \para{4-block Programs} Finally, we show how the dualization technique can by applied to solve specific 4-block integer programs (see \cref{application-to-4-block}). Furthermore, we show that they are NP-hard to approximate to any constant factor (see \cref{4-block-hardness}).
\end{enumerate}


\subparagraph*{RTC with Harmonic Periods}




We consider the decision problem $r_n \leq_? k$ for which we present a Karp reduction to the \textsc{Mixing Set} problem in constant time. However, this reduction works for large values of $k$ only, i.e. $k \geq S$ for some value $S$.
In the case of harmonic periods we managed to develop an algorithm which discovers variable values which allow to reduce $S$ such that smaller values for $k$ can be decided. To this end we prove a structural property, which, given only a rough knowledge about $r_n$, reveals the exact variable values of the variables for the tasks of largest period. The algorithm then works in two steps. First, we do a walk over the differences $p_i-\jitter_i$ in non-decreasing order to identify two consecutive differences $k_i = p_i-\jitter_i$ and $k_{i+1} = p_i-\jitter_i$ such that $r_n\in[k_i,k_{i+1}]$. Here, the order is of utmost importance, as we rely on the information of the previous decisions. In the second step we utilize a binary search to compute $r_n$. Together, this yields a Cook reduction to \textsc{Mixing Set}. We highlight this result, as it gives an efficient algorithm to the most important case of a long-standing problem (e.g.
\cite{
   
    DBLP:journals/iee/AudsleyBRTW93,%
    DBLP:journals/rts/TindellBW94,%
    DBLP:conf/rtss/DavisB08,%
   
    DBLP:conf/rtss/BonifaciMMW13,%
   
    DBLP:conf/iwoca/NguyenGJ22%
}) \todo{cite more}.
Remark that \ac{FP} scheduling superceeds the generality of \ac{DM} and \ac{RM} scheduling and in fact, we never rely on their properties.

\subparagraph*{Notation}

We define $[n]=\set{z\in\Z|1\leq z \leq n}$ to denote the set of the first $n$ natural numbers. Given a vector $v=(v_1,\dots,v_n)\in\R^n$ we denote the largest or smallest entry in $v$ by $v_{\max} = \max_{i\leq n}v_i$ or $v_{\min} = \min_{i\leq n}v_i$, respectively. For sizes $a,b$ we write $a \leq_? b$ to denote the decision problem to decide whether $a \leq b$ is true or not, i.e. the correct answer to $a \leq_? b$ is \textsc{yes} if $a \leq b$ and \textsc{no} otherwise. In the same manner we define $a \geq_? b$. For any positive integers $z_i \in \Z_{\geq 1}$ and an index set $I$ let $\lcm_{i\in I} z_i$ denote the least common multiple of all numbers in $\set{z_i|i\in I}$.

Whenever we specify the computation time of an algorithm in $\Oh$-notation, we quantify its total number of arithmetic operations on numbers from the input. With $\log=\log_2$ we always refer to the \emph{binary} logarithm.



\section{Preliminaries}

Here we introduce a dualization technique for optimization problems. Also we show first insights about the \textsc{Mixing Set} problem and present some new bounds for response times in real-time systems.

\subsection{A Dualization Technique}\label{dualision}

We present a simple optimization technique by studying a dual formulation of the associated decision problem. Consider a general optimization problem as follows.
Let $X$ be a set and let $f:X\rightarrow\Z$ and $g:X\rightarrow\R$ be two computable functions and we seek to minimize $f(x)$ over all $x\in X$ while $g(x) \geq b$ for some right-hand side $b\in\R$ and other constraints $G(x)$ have to be satisfied, i.e. we aim to compute
\[
    \sigma = \min\set{f(x)|g(x)\geq b,\;G(x),\;x \in X}.
\]
For an integer $k$ it holds that $\sigma \leq k$ if and only if
\[\addtocounter{equation}{1}\tag{\theequation}\label{dual-program-technique-dual-decision}
    \max\set{g(x)|f(x)\leq k,\;G(x),\;x\in X} \geq b.
\]
Hence, if we can bound $\sigma$ to an interval $[\ell,u]$ and have an algorithm to decide \eqref{dual-program-technique-dual-decision} in at most time $T$ for each $k\in[\ell,u]$, then we can compute $\sigma$ in time $\Oh(T\log(u-\ell))$ by using a binary search for the smallest feasible $k$ in $[\ell,u]$.
At first glance this does not help a lot, as we have replaced one optimization problem by another. However, if $f$ is a function of low complexity, then in order to decide \eqref{dual-program-technique-dual-decision} we can try to utilize an algorithm for \(\max\set{g(x)|G(x),x\in X}\) with respect to the simple additional constraint \(f(x)\leq\kappa\) (which is of low complexity). Remark that the approach may be adapted to approximate $\sigma$ for a function $f:X\rightarrow\R$ as well. However, in this paper we only care about integer-valued objectives. The technique is applied in \cref{response-time-computation,application-to-4-block}.

\subsection{Mixing Set}

Although \textsc{Mixing Set} can be solved in more general settings, for the scope of this paper we will always assume that $a\in\Z_{\geq 1}^n$ and $b\in\Z^n$. In more detail, given capacities $a\in\Z_{\geq 1}^n$, a right-hand side $b\in\Z^n$, and weights $w\in\Z_{\geq 0}^n$ (and $w_0\in\Z_{\geq 0}$) we consider the following minimization problem:
\[\label{mixing-set}
    \min\set{w_0s+\textstyle\sum_{i\leq n} w_ix_i | s+a_ix_i \geq b_i\;\forall i \in [n],\quad  s\in\Z_{\geq 0},\quad x\in\Z^n}
    \tag{\textsc{Mix}}
\]
Formally, this is not a \textsc{Mixing Set} problem, since $s\in\Z_{\geq 0}$ is required to be an integer instead of a real number. However, due to the integrality of all other numbers the relaxation to $s\in\R_{\geq 0}$ admits just the same set of \emph{optimal} solutions. From \cite{DBLP:journals/mp/ZhaoF08,DBLP:conf/ipco/ConfortiSW08,DBLP:journals/orl/ConfortiZ09} we can derive the following theorem:
\begin{theorem}[\cite{DBLP:journals/mp/ZhaoF08,DBLP:conf/ipco/ConfortiSW08,DBLP:journals/orl/ConfortiZ09}]\label{harmonic-mixing-set}
    For harmonic capacities, \eqref{mixing-set} can be computed in time $\Oh(n^2)$.
\end{theorem}
Given a value for $s$ it is obvious that $x_i = \ceil{(b_i-s)/a_i}$ for all $i\leq n$ leads to an optimal completion of $s$ to a solution $(s,x)$ to \eqref{mixing-set}. The solution $(s,x)$ might not be optimal overall but the choice of $x$ is optimal with respect to $s$. Therefore, given a solution $(s,x)$ we will assume that $x_i = \ceil{(b_i-s)/a_i}$. Furthermore, we we will write $x_i(s) = \ceil{(b_i-s)/a_i}$ (and $x(s) = (x_1(s),\dots,x_n(s))$) to denote the dependency of variable $x_i$ on $s$. Remark that by adding/subtracting the least common multiple $m = \lcm_{j\leq n} a_j$ to/from $s$ the value $x_i(s)$ is shifted by $m/a_i$ in the sense that
\[
    x_i(s\pm m)
    = \ceil[\Big]{\frac{b_i-s\mp m}{a_i}}
    = \ceil[\Big]{\frac{b_i-s}{a_i}} \mp \frac{m}{a_i}
    = x_i(s) \mp \frac{m}{a_i} \qquad \text{for all $i\leq n$.}
\]

We will depend on an upper bound on the value of $s$ in optimal solutions to \eqref{mixing-set}. Therefore, the following observations will be important.
\begin{observation}\label{mixing-set-unbounded}
    If $\sum_{i\leq n} \frac{w_i}{a_i} > w_0$, then \eqref{mixing-set} is unbounded.
    \qed
\end{observation}
\begin{proof}
    Let $m=\lcm_{i\leq n} a_i$. For any feasible solution $(s,x)$ we get another feasible solution by adding a multiple of $m$ to $s$. In particular it holds that
    \begin{align*}
        w_0(s+m) + \sum_{i\leq n} w_ix_i(s+m)
        &\;=\; w_0(s+m) + \sum_{i\leq n} w_ix_i(s) - \sum_{i\leq n} w_i\frac{m}{a_i}\\
        &\;=\; w_0 s + \sum_{i\leq n}w_ix_i(s) + m\Big(w_0 - \sum_{i\leq n} \frac{w_i}{a_i}\Big)
    \end{align*}
    and that means that solution $(s',x(s'))$ with $s' = s+m > s$ will be a truly better solution than $(s,x)$ if $\sum_{i\leq n} \frac{w_i}{a_i} > w_0$.
\end{proof}
Hence, we assume that $\sum_{i\leq n}\frac{w_i}{a_i} \leq w_0$ in general.
\begin{observation}\label{mixing-set-small-solution}
    There is an optimal solution to \eqref{mixing-set} with $s < \lcm_{i\leq n} a_i$.
\end{observation}
\begin{proof}
    Let $m=\lcm_{i\leq n} a_i$ and let $(s,x)$ be an optimal solution with $s\geq m$. We find
    \[w_0(s-m) + \sum_{i\leq n}w_ix_i(s-m) = w_0 s + \sum_{i\leq n}w_ix_i(s)-m\Big(\!\underbrace{w_0-\sum_{i\leq n}\frac{w_i}{a_i}}_{\geq\,0}\!\Big) \leq w_0 s + \sum_{i\leq n}w_ix_i(s).\]
    Hence, $(s' = s -m,x'=x(s'))$ is an optimal solution too. Iterate this argument to find an optimal solution with $s$ smaller than $m$.
\end{proof}
By using an analog contradiction proof it is easy to see that \emph{any} optimal solution will hold $s<\lcm_{i\leq n} a_i$ if $\sum_{i\leq n}\frac{w_i}{a_i}$ is truly smaller than $w_0$. We will use this strengthening:
\begin{observation}\label{mixing-set-small-utilization}
    If $\sum_{i\leq n}\frac{w_i}{a_i} < w_0$, then any optimal solution to \eqref{mixing-set} holds $s < \lcm_{i\leq n} a_i$.
\end{observation}
In \cref{lcm-bound-for-S-is-tight} we show that this bound on $s$ is tight in general.

\subsection{Response time bounds}
\label{sec:response-time-bounds}

First of all, we refine the utilization bound $\sum_{i<n}c_i/p_i < 1$. In general it holds that
\[\addtocounter{equation}{1}\tag{\theequation}\label{general-utilization-bound}
    \sum_{i<n}\frac{c_i}{p_i} \leq 1-\frac{1}{\lcm_{i<n}p_j}.
\]
To see this, let $m = \lcm_{j<n}p_j$. From $\sum_{i<n}c_i/p_i < 1$ it follows that $m\cdot\sum_{i<n}c_i/p_i < m$ and both sides of this inequality are integers which implies that $m\cdot\sum_{i<n}c_i/p_i \leq m-1$ and division by $m$ yields the claim.

In the following we give bounds to worst-case response times for both the presence and absence of task release jitters. We start with the former case.

\begin{lemma}\label{wcrt-bounds}
    It holds that $\ell \leq r_n \leq u = \min\set{u_1,u_2}$ where
    \[
        \ell = \frac{c_n+\sum_{i<n}\frac{\jitter_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}},
       
        \;
        u_1=\ell + \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}},
       
        \;
        u_2 = \ceil*{\frac{\sum_{i\leq n}c_i}{(1-\sum_{i<n}\frac{c_i}{p_i})\lcm_{i<n}p_i}}\lcm_{i<n}p_i.
    \]
\end{lemma}
\begin{proof}
    By dropping the roundings it is easy to see that
    \[
        r_n
        \;=\; c_n + \sum_{i<n} c_i\ceil*{\frac{r_n+\jitter_i}{p_i}}
        \;\geq\; c_n + r_n\sum_{i<n} \frac{c_i}{p_i} + \sum_{i<n} \frac{\jitter_i}{p_i}c_i
    \]
    which directly implies the lower bound $\ell$.
    To prove the former upper bound $u_1$ we see that
    \[
        r_n
        \;=\; c_n + \sum_{i<n}\ceil[\Big]{\frac{r_n+\jitter_i}{p_i}}c_i
        \;\leq\; c_n + \sum_{i<n}\Big(\frac{r_n+\jitter_i}{p_i}+1\Big)c_i
    \]
    and rearrangement yields
    \[
        r_n
        \;\leq\; \ell + \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        \;=\; u_1.
    \]
    To confirm the latter upper bound $u_2$ we can argue that
    $u_2 \geq (\sum_{i\leq n}c_i)/(1-\sum_{i<n}c_i/p_i)$ which implies $\sum_{i\leq n}c_i \leq u_2(1-\sum_{i<n}c_i/p_i)$ and we observe
    \begin{align*}
        c_n+\sum_{i<n}\ceil[\Big]{\frac{u_2+\jitter_i}{p_i}}c_i\;
        &=\; c_n+\sum_{i<n}\Big(\frac{u_2}{p_i}+\ceil[\Big]{\frac{\jitter_i}{p_i}}\Big)c_i\reason{$\lcm$ property}\\
        &\leq\; c_n+\sum_{i<n}\Big(\frac{u_2}{p_i}+1\Big)c_i \;=\; u_2\sum_{i<n}\frac{c_i}{p_i}+\sum_{i\leq n} c_i\reason{$0 \leq \jitter_i \leq p_i$}\\
       
        &\leq\; u_2\sum_{i<n}\frac{c_i}{p_i}+u_2\Big(1-\sum_{i<n}\frac{c_i}{p_i}\Big)
        \;=\; u_2
    \end{align*}
    which proves the claim.
\end{proof}

We will use the bound $u_1$ to show that the length of the interval $[\ell,u]$ is pseudo-polynomial and bound $u_2$ to prove that $u$ is tight. We start with the former goal.

\begin{lemma}\label{pseudo-polynomial-interval-length}
    By using only the general utilization bound it follows that $u-\ell \leq p_{\max}^n$.
    With the schedulability utilization bound it follows that $u-\ell \leq p_{\max}^2$ and even $u \leq 2p_{\max}^2$.
\end{lemma}
\begin{proof}
    Using the general utilization bound \eqref{general-utilization-bound}, i.e. $\sum_{i<n}c_i/p_i \leq 1-1/\lcm_{i<n}p_i$, it follows that $\sum_{i<n}c_i \leq p_{\max}\sum_{i<n}c_i/p_i < p_{\max}$ and
    \[
        u_1 - \ell
        = \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        \leq (\lcm_{i<n}p_i)\sum_{i<n}c_i
        \leq (\lcm_{i<n}p_i)p_{\max}
        \leq p_{\max}^n.
    \]
    Assume that $\sum_{i\leq n}c_i/p_i \leq 1$ which implies that $1/(1-\sum_{i<n}c_i/p_i) \leq p_n/c_n$. It holds that $\sum_{i\leq n}c_i \leq p_{\max}\sum_{i\leq n}c_i/p_i \leq p_{\max}$ which implies that
    \[
        u_1 - \ell
        = \frac{\sum_{i<n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = \frac{p_n}{c_n}\sum_{i<n}c_i
        \leq \frac{p_n}{c_n}p_{\max}
        \leq p_{\max}^2
    \]
    and by also using the definition of $\ell$ it follows that
    \[
        u_1
        = \frac{\sum_{i\leq n}c_i+\sum_{i<n}\frac{\jitter_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        \leq \frac{p_n}{c_n}\Big(p_{\max}+\sum_{i<n}c_i\Big)
        \leq \frac{p_n}{c_n}\cdot 2p_{\max}
        \leq 2p_{\max}^2
    \]
    and that proves the claim.
\end{proof}


\begin{lemma}\label{wcrt-upper-bound-is-tight}
    The upper bound of \cref{wcrt-bounds} is tight, even for harmonic periods.
\end{lemma}
\begin{proof}
    We set $\jitter_i=p_i$ for all $i\leq n$. According to \cref{construct-extreme-instances} we can always construct an instance with these release jitters, harmonic periods, and full utilization, i.e. $\sum_{i\leq n} \frac{c_i}{p_i} = 1$, as well as $c_n=1$ and $p_{n-1} = p_n$. Turning to \cref{wcrt-bounds} we see that such an instance holds
    \[
        \ell
        = \frac{c_n+\sum_{i<n}\frac{\jitter_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = \frac{c_n+\sum_{i<n}\frac{p_i}{p_i}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = \frac{\sum_{i\leq n}c_i}{1-\sum_{i<n}\frac{c_i}{p_i}}
        = u_2
    \]
    where the last equality follows as $\ell$ is an integer multiple of $\lcm_{i<n}p_i$ since
    \[
        \frac1{1-\sum_{i<n}\frac{c_i}{p_i}} = \frac1{\frac{c_n}{p_n}} = \frac{p_n}{c_n} = p_n = p_{n-1} = {\textstyle\max_{i<n}p_i} = \lcm_{i<n}p_i
    \]
    and that completes the proof.
\end{proof}

We want to highlight that the instances of \cref{wcrt-upper-bound-is-tight} (or \cref{construct-extreme-instances} respectively) are also extreme for the case without release jitters, i.e. $\jitter=0$. Then the tight upper bound is $P=\lcm_{i\leq n}p_i$; in fact, the upper bound of $c_n \cdot P$, which was given by Bonifaci et al. \cite[Lemma 1]{DBLP:conf/rtss/BonifaciMMW13}, can be improved to $P$. The proof is short:

\begin{lemma}\label{wcrt-bounds-without-jitters}
    If $\jitter=0$, then $c_n/(1-\sum_{i<n}\frac{c_i}{p_i}) \leq r_n \leq P$.
\end{lemma}
\begin{proof}
    The lower bound is implied by \cref{wcrt-bounds}. For the upper bound see that
    \[
        c_n+\sum_{i<n}\ceil*{\frac{P}{p_i}}c_i
        \;=\; c_n + P\cdot\sum_{i<n}\frac{c_i}{p_i}
        \;=\; p_n\cdot\frac{c_n}{p_n}+P\cdot\sum_{i<n}\frac{c_i}{p_i}
        \;\leq\; P\cdot\sum_{i=1}^{n}\frac{c_i}{p_i}
        \;\leq\; P.\qedhere
    \]
\end{proof}

\section{Response time computation}\label{response-time-computation}

We introduce a generalized problem formulation as follows. For a selection of tasks $I \subseteq [n-1]$ and an integer $\gamma\geq 1$ we aim to compute
\[\addtocounter{equation}{1}\tag{\theequation}\label{wcrt-with-jitters}
    \response(I,\gamma) = \min\set{t|t \geq \gamma + \textstyle\sum_{i\in I}\displaystyle c_i\ceil[\Big]{\frac{t+\jitter_i}{p_i}},\quad t \in \Z_{\geq 0}}.
\]
Obviously, $r_n = \response([n-1],c_n)$ is the worst-case response time of task $\tau_n$.

\subsection{Conditional Karp reduction}
\label{conditional-karp-reduction}

In the following we apply the dualization technique of \cref{dualision} to RTC. We write $x \in \Z^{I}$ to introduce a variable $x_i \in \Z$ for each $i\in I$.
Apparently, \eqref{wcrt-with-jitters} may also be stated using the following formulation as an integer linear program:
\[\label{wcrt-decision}
    \response(I,\gamma) = \min\set{t|t \geq \gamma + \textstyle\sum_{i\in I} c_ix_i,\quad p_ix_i \geq t+\jitter_i \;\forall i\in I,\quad t \in \Z_{\geq 0},\quad x \in \Z^I}
    \tag{$\response$}
\]
Let $u$ be the upper bound of \cref{wcrt-bounds} and let $k \in [u]$. One can readily verify that the associated decision problem $\response(I,\gamma) \leq_? k$ may be decided by answering $\responsedual(I,k) \geq_? \gamma$ where
\[\label{wcrt-dual}
    \responsedual(I,k) = \max\set{t-\textstyle\sum_{i\in I}c_ix_i|t \leq k,\quad p_ix_i \geq t+\jitter_i\;\forall i\in I,\quad t\in\Z_{\geq 0},\quad x\in\Z^I}.
    \tag{$\responsedual$}
\]
Let $S$ be the smallest upper bound on the value of $s$ in any optimal solution to the following instance of \textsc{Mixing Set}:
\[\label{wcrt-mixing-set}
    \mixing(I,k) = \min\set{s+\textstyle\sum_{i\in I}c_ix_i | s+p_ix_i \geq k+\jitter_i\;\forall i \in I,\quad  s\in\Z_{\geq 0},\quad x\in\Z^I}
    \tag{$\mixing$}
\]
We will prove that, if $k \geq S$ holds true, then $    \responsedual(I,k) = k-\mixing(I,k)$.
Hence, if $k$ is large enough, i.e. $k\geq S$, we can decide $\response(I,\gamma) \leq_? k$ by using the following equivalence:
\[\addtocounter{equation}{1}\tag{\theequation}\label{response-mixing-equivalence}
    \response(I,\gamma) \leq k
    \quad\Leftrightarrow\quad \responsedual(I,k) \geq \gamma
    \quad\Leftrightarrow\quad k-\mixing(I,k) \geq \gamma
    \quad\Leftrightarrow\quad \mixing(I,k) \leq k-\gamma
\]
Thus, we get the following theorem.
\begin{theorem}
    Let $I \subseteq [n-1]$ and $\gamma\in\Z_{\geq 1}$. If $k \geq S$, then there is a reduction from $\response(I,\gamma) \leq_? k$ to $\mixing(I,k) \leq_? k-\gamma$ in constant time
\end{theorem}
In the case of harmonic periods we get harmonic capacities in the instance of \textsc{Mixing Set} which implies an efficient decision algorithm. However, without further insights we can decide $\response(I,\gamma) \leq_? k$ only for large values of $k$. In \cref{wcrt-harmonic-periods} we describe how to overcome this issue in the case of harmonic periods.

If $k \geq S$ holds, remark that optimal solutions to \eqref{wcrt-mixing-set} also do hold $x \in \Z_{\geq 0}^I$, since $s \leq S \leq k$ which implies $x_i = \ceil{(k-s+\jitter_i)/p_i} \geq \ceil{\jitter_i/p_i} \geq 0$ for all $i\in I$. By using \cref{mixing-set-small-utilization} it holds that $S \leq \lcm_{i\in I}p_i$, since $\sum_{i\in I} \frac{c_i}{p_i} \leq \sum_{i<n} \frac{c_i}{p_i} < 1$.

\begin{lemma}\label{reduction-to-mixing-set}
    If $k \geq S$, then $\responsedual(I,k) = k-\mixing(I,k)$.
\end{lemma}
\begin{proof}
    Let $(t,x)$ be an optimal solution to \eqref{wcrt-dual}
    with objective value $k-\sigma$ for some value $\sigma$. We know that $0 \leq t \leq k$. Then by setting $s = k-t \geq 0$ we see that $(s,x)$ is a solution to \eqref{wcrt-mixing-set} since $s+p_ix_i = k-t+p_ix_i \geq k-t+t+\jitter_i = k+\jitter_i$. Its objective value is
    \[
        s+\sum_{i\in I} c_ix_i
        = k - t + \sum_{i\in I} c_ix_i
        = k-\Big(t-\sum_{i\in I} c_ix_i\Big)
        = k-(k-\sigma)
        = \sigma.
    \]
    Vice-versa let $(s,x)$ be an optimal solution to \eqref{wcrt-mixing-set} with objective value $\sigma$. We know that $0 \leq s \leq S \leq k$. Hence, by setting $t = k-s \geq 0$ we see that $(t,x)$ is a solution to \eqref{wcrt-dual} since $t+\jitter_i = k-s+\jitter_i = k+\jitter_i-s \leq s+p_ix_i -s = p_ix_i$
    and $t = k-s \leq k$. Its objective value is
    \[
        t-\sum_{i\in I} c_ix_i
        = k-s - \sum_{i\in I} c_ix_i
        = k-\Big(s+\sum_{i\in I} c_ix_i\Big)
        = k - \sigma
    \]
    and that proves the claim.
\end{proof}


\subsection{Harmonic Periods}\label{wcrt-harmonic-periods}

Here we assume harmonic periods, i.e. $p_i\geq p_j$ implies $p_i/p_j \in \Z$ for all $i,j \in I$. A direct consequence is that $\lcm_{i \in I}p_i = \max_{i\in I} p_i$. Also it holds that $u \leq u_2 \leq p_{\max}\sum_{i\leq n} c_i \leq 2p_{\max}^2$.
By using the described reduction to the \textsc{Mixing Set} instance \eqref{wcrt-mixing-set} and solving it in time $\Oh(n^2)$ using \cref{harmonic-mixing-set} we get the following result.
\begin{theorem}\label{large-k-is-okay}
    Let $I \subseteq [n-1]$ and $\gamma\in\Z_{\geq 1}$. If $k \geq \max_{i\in I}p_i$, then $\response(I,\gamma) \leq_? k$ can be decided in time $\Oh(n^2)$
\end{theorem}
Obviously, by itself \cref{large-k-is-okay} does not allow to binary search for the optimal solution in general, since we do not know how to find it if it is smaller than $\max_{i\in I}p_i$. For now, we only see that we can utilize a binary search to get the following corollary.

\begin{corollary}
    Let $t^*$ be the optimum value to \eqref{wcrt-decision}. If $t^* \geq \max_{i\in I}p_i$, then $t^*$ can be computed in time $\Oh(n^2\log p_{\max})$
\end{corollary}

However, if the values for the variables of the tasks with the largest periods are known \emph{a priori}, then the largest period of the residual instance will be smaller than before and we can decide even lower values of $k$. In fact, for tasks $\tau_i$ with large periods a rough knowledge about the optimum value suffices to find the exact value of the variables $x_i$. The following lemma will be crucial to exploit this idea (see also \cref{fig:two-possible-situations}).

\begin{lemma}\label{two-values}
    Let $(t,x)$ be an optimal solution to \eqref{wcrt-decision}. If $0 < t \leq p_i$ for some $i\in I$, then
    \[x_i = \begin{cases}1 &: t \leq p_i-\jitter_i\\2 &: t > p_i-\jitter_i\end{cases}.\]
\end{lemma}
\begin{proof}
    Since $(t,x)$ is an optimal solution, we know that $x_i = \ceil{(t+\jitter_i)/p_i}$.
    Now, if we are in the case that $t \leq p_i-\jitter_i$, then
    $0 < (t+\jitter_i)/p_i \leq (p_i-\jitter_i+\jitter_i)/p_i = 1$
    and if $p_i-\jitter_i < t$, then
    $1 = (p_i-\jitter_i+\jitter_i)/p_i < (t+\jitter_i)/p_i \leq (p_i+p_i)/p_i = 2$
    which proves the claim.
\end{proof}

\begin{figure}
    \centering
    \tikz[xscale=0.7,yscale=0.15]{
        \draw (0,1) -- (0,-1) node [below] {$0$};
        \draw (0,0) -- (18,0);
        \draw (10,1) -- (10,-1) node [below] {$p_j-\jitter_j$};
        \draw (6,1) -- (6,-1) node [below] {$k_i$};
        \draw (18,1) -- (18,-1) node [below] {$p_j$};
        \draw [|-|,draw=gray] (0,3) -- node [above] {$x_j = 1$} (10,3);
        \draw [|-|,draw=gray] (10,3) -- node [above] {$x_j = 2$} (18,3);
        \begin{scope}[shift={(0,-11)}]
            \draw (0,1) -- (0,-1) node [below] {$0$};
            \draw (0,0) -- (18,0);
            \draw (3,1) -- (3,-1) node [below] {$p_j-\jitter_j$};
            \draw (6,1) -- (6,-1) node [below] {$k_i$};
            \draw (18,1) -- (18,-1) node [below] {$p_j$};
            \draw [|-|,draw=gray] (0,3) -- node [above] {$x_j = 1$} (3,3);
            \draw [|-|,draw=gray] (3,3) -- node [above] {$x_j = 2$} (18,3);
        \end{scope}
    }
    \caption{Two possible situations; the former is simple while the latter is complicated}
    \label{fig:two-possible-situations}
\end{figure}

To describe our algorithm in detail, we consider integers $k_0 = 0$, $k_{q+1}=u$, as well as $0< k_1 < \dots < k_q$ with $\set{k_1,\dots,k_q}=\set{p_j-\jitter_j|j\in I}\setminus\set{0}$ where $q \leq \abs{I}$. Our algorithm walks over these differences \enquote{from left to right}, starting with the smallest difference $p_j-\jitter_j$. Powered by the invariants \cref{first-invariant,catch-search}, it discovers variable values; in fact, the tasks whose variables are identified to have value $1$ are stored in the set $I_1$ while those which are known to have value $2$ are stored in set $I_2$.

\noindent\begin{minipage}[t]{0.52\textwidth}
\begin{myalgorithm}{\textsc{Narrow}}
\setstretch{1.5}
\begin{algorithmic}[1]
    \For{$i=1,\dots,q$}
        \State $I_1 \gets \set{j\in I|k_i \leq p_j-\jitter_j}$
        \State $I_2 \gets \set{j\in I|p_j-\jitter_j < k_i \leq p_j}$
        \State $\gamma_i \gets \gamma + \sum_{v\in\{1,2\}}\sum_{j\in I_v}vc_j$
       
        \If{$\mixing(I\setminus(I_1\cup I_2),k_i) \leq k_i-\gamma_i$}
            \State \Return $\ref{alg:catch}(k_{i-1}+1,k_i)$
        \EndIf
    \EndFor
    \State \Return $\ref{alg:catch}(k_q+1,u)$
\end{algorithmic}
\caption{\!\!\(\)}
\label{alg:narrow}
\end{myalgorithm}
\end{minipage}
\hfill
\begin{minipage}[t]{0.46\textwidth}
\begin{myalgorithm}{\textsc{Catch}}
\setstretch{1.035}
\begin{algorithmic}[1]
    \State $I_1 \gets \set{j\in I|R\leq p_j-\jitter_j}$
   
    \While{$L \neq R$}
        \State $\kappa \gets \floor{(L+R)/2}$
       
        \State $I_2 \gets \set{j\in I|\kappa \leq p_j < L+\jitter_j}$
       
        \State $\gamma'_{\kappa} \gets \gamma + \sum_{v\in\{1,2\}}\sum_{j\in I_v}vc_j$
       
        \If{$\mixing(I\setminus(I_1\cup I_2),\kappa) \leq \kappa - \gamma'_{\kappa}$}
            \State $R \gets \kappa$
        \Else
            \State $L \gets \kappa+1$
        \EndIf
    \EndWhile
    \State \Return $R$
\end{algorithmic}
\caption{\!\!\((L,R)\)}
\label{alg:catch}
\end{myalgorithm}
\medskip
\end{minipage}
\begin{figure}
    \centering
    \tikz[xscale=0.35,yscale=0.18]{
        \draw [black!30!red] (9,0) -- (18,0);
        \draw [black!50!green] (26,0) -- (42,0);
        \draw (20,1) -- (20,-1) node [below] {$p_a$};
        \draw (23,1) -- (23,-1) node [below] {$p_b$};
        \draw [fill=blue!50!white] (18,-.3) rectangle (26,.3);
        \draw (18,1) -- (18,-1) node [below,black!30!red] {$k_{i-1}$};
        \draw (31,1) -- (31,-1) node [below] {$p_c$};
        \draw (33,1) -- (33,-1) node [below] {$p_d$};
        \draw (37,1) -- (37,-1) node [below] {$p_e$};
        \draw (40,1) -- (40,-1) node [below=-0.3] {$p_f$};
        \draw (26,1) -- (26,-1) node [below,black!50!green] {$k_i$};
       
        \draw [|-|,draw=gray] (12,6) -- node [above] {$x_a = 2$} (20,6);
        \draw [|-|,draw=gray] (18,3) -- node [above] {$x_b = 2$} (23,3);
        \draw [|-|,draw=gray] (27,6) -- node [above] {$x_c = 2$} (31,6);
        \draw [|-|,draw=gray] (26,3) -- node [above] {$x_d = 2$} (33,3);
        \draw [|-|,draw=gray] (18,-4) -- node [below] {$x_e = 2$} (37,-4);
        \draw [|-|,draw=gray] (14,-7) -- node [below] {$x_f = 2$} (40,-7);
    }
    \caption{A ($\log$-scaled) example where $k_i$ is feasible while $k_{i-1}$ is not, i.e. $k_{i-1} < \response(I,\gamma) \leq k_i$}
    \label{fig:second-search}
\end{figure}
So, the algorithm works in two steps. The first one is to identify the interval $(k_{i-1},k_i]$ which contains the desired response time (\cref{alg:narrow}). The second step is to use a binary search inside this interval to find the exact response time (\cref{alg:catch}). We heavily use the fact, that \emph{any} solution which gives a \textsc{yes} answer to the decision problem $\response(I,\gamma) \leq_? k$ is smaller than $k$. The correctness of the algorithm crucially depends on the following two invariants.

\begin{lemma}[Invariant]\label{first-invariant}
    For each iteration $i\in[q]$ of \cref{alg:narrow} and each $j\in I$ with $k_i \leq p_j$ the value for variable $x_j$ is known a priori.
\end{lemma}
\begin{proof}
    We do a case distinction as follows. If $k_i \leq p_j-\jitter_j$, then by \cref{two-values} we know that $x_j=1$. If otherwise $k_i > p_j-\jitter_j$, then by the order of the algorithm we know that there is an index $i' < i$ such that we already have checked $k_{i'} = p_j-\jitter_j < k_i$ and $k_{i'}$ was not feasible. Hence, any feasible solution $t$ has to be truly greater than $k_{i'} = p_j-\jitter_j$ and by \cref{two-values} we know that $x_j = 2$.
\end{proof}

\begin{lemma}[Invariant]\label{catch-search}
    For each iteration $\kappa \in [L,R]$ of \cref{alg:catch} and each $j \in I$ with $\kappa \leq p_j$ the value for variable $x_j$ is known a priori.
\end{lemma}
\begin{proof}
    Remark that $k_i \notin [L,R)$ for each $i\in I$. We do a case distinction as follows. If $R \leq p_j$, then $x_j = 1$ if $R \leq p_j-\jitter_j$ and $x_j = 2$ otherwise (if $p_j-\jitter_j < R$ which implies $p_j-\jitter_j \leq L)$. If $\kappa \leq p_j < R$, then $p_j-\jitter_j < L$ which implies $x_j=2$.
\end{proof}

\Cref{fig:second-search} gives an example to see that in the second step all variable values for tasks with periods above $\kappa$ are known a priori. The key property is, that by the definition of $k_1,\dots,k_q$ there is no difference $p_j-\jitter_j$ inside of the interval $(k_{i-1},k_i)$ for any task $\tau_j$.

\begin{lemma}\label{narrowing-correctness}
    Let $i \in [q]$. If $\response(I,\gamma) > k_j$ for any $j<i$, then $\response(I,\gamma) \leq_? k_i$ can be decided in time $\Oh(n^2)$.
\end{lemma}
\begin{proof}
    Consider the task sets $I_1 = \set{j\in I|k_i \leq p_j-\jitter_j}$, $I_2 = \set{j\in I|p_j-\jitter_j < k_i \leq p_j}$, and $I_* = \set{j\in I|p_j<k_i}$ such that $I_* = I \setminus (I_1 \cupdot I_2)$. Then by using \cref{first-invariant} and setting $\gamma' = \gamma + \sum_{v\in\{1,2\},j\in I_v}vc_j$ the decision problem $\response(I,\gamma) \leq_? k_i$ simplifies to $\response(I_*,\gamma') \leq_? k_i$ as all variables for the tasks in $I_1$ have value $1$ and the variables for the tasks in $I_2$ have value $2$. By definition, all periods of the remaining tasks $I_*$ are smaller than $k_i$, i.e. $k_i \geq \max_{j\in I_*}p_j$. Therefore, by using \eqref{response-mixing-equivalence} again we can solve the \textsc{Mixing Set} problem $\mixing(I_*,k_i)$ to find the correct decision for $\response(I,\gamma) \leq_? k_i$ in time $\Oh(n^2)$.
\end{proof}

By \cref{narrowing-correctness} we see that \cref{alg:narrow} correctly narrows the response time candidate interval $(0,u]$ down to some interval $[L,R]$ such that $L = k_{i-1}+1$ and $R=k_i$ for some $i\in[q+1]$. The correctness of the subsequent binary search in \cref{alg:catch} is then implied by \cref{catch-search}. Together we get the following result.

\begin{theorem}\label{harmonic-result}
    Let $I \subseteq [n-1]$ and $\gamma\in\Z_{\geq 1}$. In the case of harmonic periods $\response(I,\gamma)$ can be computed in time $\Oh(q\cdot \abs{I}^2+\abs{I}^2\log p_{\max})$ where $q=\abs{\set{p_i-\jitter_i|i\in I}}$.
\end{theorem}

Note that the running time improves to strongly polynomial time $\Oh(q\abs{I}^2)$ if $\log(p_{\max}) \leq \Oh(q)$ and to $\Oh(\abs{I}^2\log p_{\max})$ otherwise.

    
    


\subsection{Arbitrary Periods}
\label{wcrt-arbitrary-periods}

For the ease of notation and w.l.o.g. we consider $I=[n-1]$ and $\gamma = c_n$ here.
The following theorem reveals a first simple algorithm to compute worst-case response times for general periods in pseudo-polynomial time.

\begin{theorem}
    The worst-case response time $r_n$ can be computed in time $\Oh(n\cdot\lcm_{i<n}p_i)$.
\end{theorem}
\begin{proof}
    Let $m=\lcm_{i<n}p_i$ and define $w(t) = c_n+\sum_{i<n}c_i\ceil{\frac{t+\jitter_i}{p_i}}$. Then there is a remainder $\rho \in \set{0,\dots,m-1}$ and some $\lambda \in \Z_{\geq 0}$ such that $r_n = \rho+\lambda m$. We find that
    \[
        \rho+\lambda m
        \;=\; r_n
        \;=\; w(r_n)
        \;=\; w(\rho+\lambda m)
        \;=\; w(\rho)+\lambda m\cdot\sum_{i<n}\frac{c_i}{p_i}
    \]
    and thus, $\lambda = (w(\rho)-\rho)/((1-\sum_{i<n}\frac{c_i}{p_i})\cdot m)$ can be computed in time $\Oh(n)$ for a given $\rho$. Hence, we can compute $r_n$ by simply trying each $\rho$ in $\set{0,\dots,m-1}$ and compute $\lambda$ for this choice to find the smallest sum $\rho+\lambda m$ for which the computed $\lambda$ is a non-negative integer. This yields a total running time of $\Oh(n\cdot m)$.
\end{proof}

However, by using our reduction we can prove a Turing reduction as follows.

\begin{theorem}
    The response time $r_n$ can be computed in time $\Oh(\max(Sn,T_{\mixing}\log p_{\max})) \leq \Oh(Sn\log p_{\max})$ where $S$ is a global upper bound on variable $s$ in any optimal solution to \eqref{wcrt-mixing-set} and $T_{\mixing}$ is a global upper bound on the running time required to compute \eqref{wcrt-mixing-set}.
\end{theorem}
\begin{proof}
    We may run an algorithm as follows. First decide $\response(I,\gamma) \leq_? S$. If the answer is \textsc{yes}, then try out all candidates $t\in[S-1]$ in time $\Oh(Sn)$, i.e. we check whether $t$ is a solution to \eqref{wcrt-with-jitters-original}.
    If this reveals a feasible solution, return the smallest. Otherwise $r_n = S$. If the answer is \textsc{no}, then it holds that $r_n > S$.
    From \cref{pseudo-polynomial-interval-length} we know that $u - \ell \leq p_{\max}^2$ and thus, a subsequent binary search in $[\ell,u]$ leads to a total running time of $\Oh(\max(Sn,T_{\mixing}\log(u-\ell))) \leq \Oh(\max(Sn,T_{\mixing}\log p_{\max}))$. For example we can bound $T_{\mixing}$ as follows.
    We can compute $\mixing([n-1],k)$ in time $\Oh(Sn)$ by simply trying solution $(s,x(s))$ for each $s\in [0,S)$. Hence, $T_{\mixing} \leq \Oh(Sn)$ and this gives a total running time of $\Oh(Sn\log p_{\max})$.
\end{proof}

In the case without task release jitter, i.e. $\jitter_i = 0$ for all $i\in I$, we can even prove an \emph{unconditional} Karp reduction as follows. For $\jitter = 0$ we get the following form of \eqref{wcrt-mixing-set}:
\[\label{wcrt-mixing-set-without-jitter}
    \mixing_{\jitter=0}(I,k) = \min\set{s+\textstyle\sum_{i\in I}c_ix_i | s+p_ix_i \geq k\;\forall i \in I,\quad  s\in\Z_{\geq 0},\quad x\in\Z^I}
    \tag{$\mixing_{\jitter=0}$}
\]
In this case we can show that $S \leq k$. Apparently, $(s=k,x=0)$ is always a solution to \eqref{wcrt-mixing-set-without-jitter} since $s+p_ix_i = k$. It has the objective value $s+\sum_{i\in I}c_ix_i = k$. Any solution $(s,x)$ to \eqref{wcrt-mixing-set-without-jitter} with $s>k$ has an objective value truly larger than $k$, since
\[
    s+\sum_{i\in I}c_ix_i(s)
    \;=\; s+\sum_{i\in I}c_i\ceil*{\frac{k-s}{p_i}}
    \;\geq\; s+\underbrace{(k-s)}_{<\,0}\cdot\underbrace{\sum_{i\in I}\frac{c_i}{p_i}}_{<\,1}
    \;>\; s+(k-s)\cdot 1
    \;=\; k.
\]
Hence, any optimal solution $(s,x)$ to \eqref{wcrt-mixing-set-without-jitter} holds $s \leq k$ which implies that $S \leq k$.

Therefore, $\responsedual(I,k) = k-\mixing(I,k)$ is directly implied. Thus, we can use a binary search to compute $r_n$ in time $\Oh(T_{\mixing}\log p_{\max})$ where $T_{\mixing}$ is a global upper bound on the time required to compute $\mixing(I,k)$. This yields the following result.

\begin{theorem}
    If $\jitter=0$, then $r_n$ can be computed in time $\Oh(T_{\mixing}\log p_{\max})$ where $T_{\mixing}$ is a global upper bound on the time required to compute \eqref{wcrt-mixing-set}.
\end{theorem}

\subparagraph*{Small Utilization}
As for \ac{RM} scheduling (cf. \cite{DBLP:journals/jacm/LiuL73,DBLP:conf/afips/Serlin72}) the complexity of RTC decreases with a smaller utilization  also for \ac{FP} scheduling. Let $U = \sum_{i<n}c_i/p_i$ denote the utilization.

\begin{lemma}\label{bound-S-with-utilization}
    In general it holds that $S \leq (\sum_{i<n}c_i)/(1-U)$.
    \qed
\end{lemma}
\begin{proof}
    Let $S' = (\sum_{i< n}c_i)/(1-U)$, set $f(s) = s+\sum_{i<n}c_ix_i(s)$ as the objective function of $\mixing(I,k)$, and assume that $s \geq S'$ is a solution to $\mixing(I,k)$. Then
    \begin{align*}
        f(s-S')
        &= s-S' + \sum_{i<n}c_i\ceil[\Big]{\frac{k+\jitter_i-s+S'}{p_i}}\\
        &\leq s - S' + \sum_{i<n}c_i\Big(\ceil[\Big]{\frac{k+\jitter_i-s}{p_i}}+\ceil[\Big]{\frac{S'}{p_i}}\Big)\\
        &= f(s) - S' + \sum_{i<n}c_i\ceil[\Big]{\frac{S'}{p_i}}
        < f(s) - S' + \sum_{i<n}c_i\Big(\frac{S'}{p_i}+1\Big)
        = f(s)
    \end{align*}
    which implies that $s' = s-S'$ is a truly better solution to $\mixing(I,k)$.
\end{proof}
Using the schedulability utilization bound this immediately assures that $S$ is pseudo-polynomial using only the general utilization bound it suffices for example that $U \leq 1-p_{\max}^{-\Oh(1)}$. Since $u_1-\ell = (\sum_{i<n}c_i)/(1-U)$ this also implies a pseudo-polynomial algorithm by simply guessing the right value in in the interval $[\ell,u]$. However, especially if $r_n > S$ our algorithm may be faster.

\section{Mixing Set}
\label{sec:mixing-set}

Our technique may be reversed to solve the \textsc{Mixing Set} problem by computing worst-case response times. This allows us to make efficient approaches to RTC applicable to solve \textsc{Mixing Set}. We simply do a substitution in \eqref{response-mixing-equivalence} (substitute $k \mapsto k'+\gamma$, $\gamma \mapsto \beta - k'$, $k' \mapsto k$ in this order) to achieve the following corollary.

\begin{corollary}\label{reverse-reduction}
    Let $\beta \geq S$. Then $\mixing(I,\beta) \leq k$ if and only if $\response(I,\beta-k) \leq \beta$.
\end{corollary}

With the reverse reduction we can improve the running time for general capacities, if the entries of the right-hand side $b$ are large and close to $b_{\min}$:

\begin{lemma}\label{mixing-set-with-large-crowded-right-hand-side}
    Given capacities $a\in\Z_{\geq 1}^n$, a right-hand side $b\in\Z^n$ which holds that $\lcm_{j\leq n} a_j \leq b_i \leq b_{\min}+a_i$ for all $i\leq n$, and weights $w \in \Z_{\geq 0}^n$, one can compute
    \[\label{mixing-with-crowded-right-hand-side}
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq b_i\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_b$}
    \]
    in time $\Oh(T_{\response}\log b_{\max})$ where $T_{\response}$ is a global upper bound on the time required to compute \eqref{wcrt-decision}.
\end{lemma}
\begin{proof}
    Choose $\beta = b_{\min}$ and $\jitter_i = b_i - b_{\min}$ for all $i \in [n]$. We get $\beta \geq \lcm_{i\leq n} a_i \geq S$ and $0 \leq \jitter_i \leq a_i$ for all $i\leq n$. This implies $b_i = \beta + \jitter_i$ and thus, we can write \eqref{mixing-with-crowded-right-hand-side} as
    \[
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq \beta+\jitter_i\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}.
    \]
    Now, we use \cref{reverse-reduction} to start a binary search for the optimal $k$. We know that $\response([n],\beta-k)$ can be computed in time $T_{\response}$ and the objective value of our \textsc{Mixing Set} instance is upper bounded by $b_{\max}$ (since $(s=b_{\max},x=0)$ is always a solution with objective value $b_{\max}$) which implies a total running time of $\Oh(T_{\response}\log b_{\max})$.
\end{proof}
In fact, \cref{mixing-set-with-large-crowded-right-hand-side} implicitly solves the general case. We use it to prove the following.
\begin{theorem}
    Given capacities $a\in\Z_{\geq 1}^n$, a right-hand side $b\in\Z^n$, and weights $w \in \Z_{\geq 0}^n$, one can compute
    \[
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq b_i\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_b$}
    \]
    in time $\Oh(n+T_{\response}\log b_{\max})$ where $T_{\response}$ is a global upper bound on the time required to compute \eqref{wcrt-decision}.
\end{theorem}
\begin{proof}
    Let $m = \lcm_{j\leq n}a_j$. We define a new right-hand side $b' \in \Z^n$ by
    \[
        b_i' = b_i + \ceil*{\frac{m - b_i}{a_i}}a_i
    \]
    for each $i\leq n$. It is easy to see that $m \leq b_i' \leq m+a_i \leq b'_{\min}+a_i$ for all $i\leq n$. Also, we have
    \begin{align*}
        &\min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i \geq b'_i\forall i\leq n, s\in\Z_{\geq 0},x\in\Z^n}\\
        &= \min\set{s+\sum_{i\leq n}w_i\ceil*{\frac{b'_i-s}{a_i}}| s\in\Z_{\geq 0}}\\
        &= \min\set{s+\sum_{i\leq n}w_i\ceil*{\frac{b_i + \ceil*{\frac{m - b_i}{a_i}}a_i-s}{a_i}}| s\in\Z_{\geq 0}}\\
        &= \sum_{i\leq n}w_i\ceil*{\frac{m - b_i}{a_i}} + \min\set{s+\sum_{i\leq n}w_i\ceil*{\frac{b_i-s}{a_i}}| s\in\Z_{\geq 0}}\\
        &= \sum_{i\leq n}w_i\ceil*{\frac{m - b_i}{a_i}} + \min\set{s+\sum_{i\leq n}w_ix_i| s+a_ix_i \geq b_i\forall i\leq n, s\in\Z_{\geq 0},x\in\Z^n}
    \end{align*}
    Hence, we can solve the system for $b'$ with \cref{mixing-set-with-large-crowded-right-hand-side} and subtract $\sum_{i\leq n}w_i\ceil{(m - b_i)/a_i}$ to obtain the optimal value. This gives the desired running time.
\end{proof}

Now, we aim to identify the instances of \textsc{Mixing Set} which may be solved by using our reversed reduction in combination with efficient algorithms for the computation of worst-case response times. By turning to harmonic periods $p_i$ and using \cref{reverse-reduction} again, we can apply Nguyen et al. \cite{DBLP:conf/iwoca/NguyenGJ22} to compute
\[
    \min\set{s+\sum_{i\in I}c_ix_i|s+p_ix_i\geq \beta\;\forall i\in I,\quad s\in\Z_{\geq 0},\quad x\in\Z^I}
\]
in time $\Oh(n\log n+n\log\beta)$ for any $\beta \geq \max_{i \in I} p_i$ by computing the response times
\[
    \min\set{t|t \geq \beta - k + \textstyle\sum_{i\in I} \ceil[\big]{\frac{t}{p_i}}c_i,\quad t \in \Z_{\geq 0}}
\]
in a binary search for the smallest feasible $k$. It suffices to search in the interval $[0,\beta]$ since $(s=\beta,x=0)$ is always a solution with value $\beta$. Remark that the usual running time to solve instances of \textsc{Mixing Set} with harmonic capacities is $\Oh(n^2)$. In a more classical formulation this yields the following theorem.

\begin{theorem}
    Given harmonic capacities $a\in\Z_{\geq 1}^n$, a right-hand side value $\beta\geq a_{\max}$, and weights $w \in \Z_{\geq 0}$, one can compute
    \[\label{mixing-beta}
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq \beta\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_{\beta}$}
    \]
    in time $\Oh(n\log n+n\log\beta) \leq \Oh(n\log(n+\beta))$.
\end{theorem}

The algorithm of Nguyen et al. runs in linear time $\Oh(n)$ after an initial sorting step in time $\Oh(n\log n)$ to sort the tasks by their periods. As we seek to apply the algorithm multiple times, we can save the time to sort by only doing it once.

However, for arbitrary capacities and the special case $b_i=\beta$ for all $i\leq n$ and $\beta \geq \lcm_{j\leq n}a_j$ we can also derive the following corollary from \cref{mixing-set-with-large-crowded-right-hand-side}.
\begin{corollary}
    Given capacities $a\in\Z_{\geq 1}^n$, a right-hand side value $\beta\geq\lcm_{i\leq n}a_i$, and weights $w \in \Z_{\geq 0}^n$, one can compute
    \[
        \min\set{s+\sum_{i\leq n}w_ix_i|s+a_ix_i\geq \beta\;\forall i\leq n,\quad s\in\Z_{\geq 0},\quad x\in\Z^n}\tag{$\mixing_b$}
    \]
    in time $\Oh(T_{\response}\log\beta)$ where $T_{\response}$ is a global upper bound on the time required to compute \eqref{wcrt-decision}.
\end{corollary}

\section{4-block Integer Programming}
\label{application-to-4-block}

Block-structured integer programming has received major interest in the recent past. Namely, the three most important lines of research are $n$-fold integer programming, $2$-stage stochastic integer programming, and $4$-block integer programming \cite{DBLP:conf/icalp/EisenbrandHK18,DBLP:conf/esa/0009K0S20,arxiv/2201.05874,DBLP:conf/ipco/HemmeckeKW10}. The latter is the most general but also the least understood flavor of block-structured integer programs. In this section we will consider 4-block integer programs with only one coupling constraint inequality. Furthermore, we consider a simpler objective function which addresses at most two \emph{bricks}. From \cref{4-block-hardness} it follows that this problem is still hard to approximate to any constant factor.
In fact, the literature on $4$-block integer programs is not unified in its formal presentation. Here we consider $4$-block integer programs as follows.

Consider matrices $A_1,\dots,A_n$, $B_1,\dots,B_n$, $C_1,\dots C_n$, and $D$ such that $A_i \in \Z^{r\times t}$, $B_i \in \Z^{r\times s}$, and $C_i\in\Z^{q\times t}$ for all $i\in[n]$ and $D\in\Z^{q\times s}$. We aim to compute
\[\addtocounter{equation}{1}\tag{\theequation}\label{4-block}
    \min\set{w^\intercal x|\mathcal{B}x = b, \quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}}
\]
where
\[
    \mathcal{B}=\begin{pmatrix}
        D&C_1&\cdots&C_n\\
        B_1&A_1\\
        \vdots&&\ddots\\
        B_n&&&A_n
    \end{pmatrix}.
\]

We use the notion of \emph{bricks} $w^{(0)},w^{(1)},\dots,w^{(n)}$ and $x^{(0)},x^{(1)},\dots,x^{(n)}$ to refer to different areas of $w$ and $x$. For each $i\in\set{1,\dots,n}$ let $w^{(i)} = (w_{(i-1)t+1},\dots,w_{it})$ and $x^{(i)} = (x_{(i-1)t+1},\dots,x_{it})$ denote the $i$-th bricks of $w$ and $x$. Furthermore, let $w^{(0)} = (w_1,\dots,w_s)$ and $x^{(0)} = (x_1,\dots,x_s)$ denote the $0$-th bricks of $w$ and $x$.

In the following we assume that there is exactly one coupling constraint \emph{inequality} and that there is a $j \in [n]$ such that $w^{(i)}=0$ for all $i\in[n]\setminus\set{j}$. In other words, the objective function addresses exactly two bricks of the solution and at least one of them is the first brick.
Let $a \in \Z^{s+nt}$ denote the first row of $\mathcal{B}$. We aim to compute
\[\addtocounter{equation}{1}\tag{\theequation}\label{simple-4-block}
    \tau=\min\set{w^\intercal x|a^\intercal x \geq b_0,\quad\mathcal{B}'x = b, \quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}}
\]
where
\[
    \mathcal{B}'=\begin{pmatrix}C_1&B_1\\\vdots&&\ddots\\C_n&&&B_n\end{pmatrix}.
\]
For the decision problem $\tau \leq_? k$ we get the following dual formulation:
\[
    \max\set{a^\intercal x|w^\intercal x\leq k,\quad\mathcal{B}'x = b,\quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}} \geq_? b_0
\]
Introduce a slack variable $y\geq 0$ to replace the inequality \enquote{$w^\intercal x\leq k$} with the equation \enquote{$w^\intercal x+y = k$}:
\[
    \max\set{a^\intercal x|w^\intercal x+y= k,\quad\mathcal{B}'x = b,\quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}, \quad y \in \Z_{\geq 0}}
\]
By placing the additional constraint \enquote{$w^\intercal x+y=k$} on top of the $j$-th block matrices we get a new matrix
\[
    \mathcal{B}''=\begin{pmatrix}
         \tikz[scale=0.8]{
            \draw (0,4) rectangle node {$C_1$} (1,5);
            \draw (1,4) rectangle node {$B_1$} (2,5);
            \draw (0,3) rectangle node {$\overbar{w}^{(0)}$} (1,3.4);
            \draw (4,3) rectangle node {$1$} (4.4,3.4);
            \draw (3,3) rectangle node {$\overbar{w}^{(j)}$} (4,3.4);
            \draw (0,2) rectangle node {$C_j$} (1,3);
            \draw [dashed] (4,2) -- (4.4,2) -- (4.4,3);
            \draw (3,2) rectangle node {$B_j$} (4,3);
            \draw (0,0) rectangle node {$C_n$} (1,1);
            \draw (5,0) rectangle node {$B_n$} (6,1);
         }
    \end{pmatrix}
\]
where $\overbar{w}^{(0)}=(w^{(0)})^\intercal$ and $\overbar{w}^{(j)}=(w^{(j)})^\intercal$. Finally, we arrive at the $2$-stage stochastic integer program
\[\addtocounter{equation}{1}\tag{\theequation}\label{2-stage}
    \max\set{a^\intercal x|\mathcal{B}''x = b',\quad 0 \leq x \leq u, \quad x\in \Z^{s+nt}, \quad y \in \Z_{\geq 0}}
\]
where $b'$ is the modified right-hand side with value $k$.
Use, for example, \cite{DBLP:conf/esa/CslovjecsekEPVW21} to solve it.

\begin{theorem}
    Program \eqref{simple-4-block} can be solved in time $\Oh(T_{\eqref{2-stage}}\cdot\log(2H))$ where $T_{\eqref{2-stage}}$ is a global upper bound on the time to solve \eqref{2-stage} and $H$ is an upper bound on the absolute objective value of an optimal solution to \eqref{simple-4-block}.
\end{theorem}

Using the state-of-the-art algorithm for 2-stage stochastic integer programming by Cslovjecsek et al. \cite{DBLP:conf/esa/CslovjecsekEPVW21} we can bound $T_2 \leq 2^{(2\Delta)^{\Oh(s(s+t))}}\cdot\log^{\Oh(st)}n$ by using parallel computation where $\Delta = \max\set{\norm{\mathcal{B}}_{\infty},\norm{w}_{\infty}}$ is the largest absolute value of the entries in $\mathcal{B}$ and $w$.
To give a simple bound on $H$ one can use standard arguments (e.g. \cite[Theorem 13.5]{DBLP:books/ph/PapadimitriouS82}) to show that $\log(2H) \leq \Oh(\log(st\norm{w}_1\norm{b}_{\infty})+(nr+q)\log((nr+q)\norm{A}_{\infty}))$.




