# Lower Bound on Irreversibility in Thermal Relaxation of Open Quantum Systems

Tan Van Vu<EMAIL_ADDRESS>Department of Information and
Communication Engineering, Graduate School of Information Science and
Technology, The University of Tokyo, Tokyo 113-8656, Japan  Yoshihiko Hasegawa
<EMAIL_ADDRESS>Department of Information and Communication
Engineering, Graduate School of Information Science and Technology, The
University of Tokyo, Tokyo 113-8656, Japan

###### Abstract

We consider the thermal relaxation process of a quantum system attached to
single or multiple reservoirs. Quantifying the degree of irreversibility by
entropy production, we prove that the irreversibility of the thermal
relaxation is lower-bounded by a relative entropy between the unitarily-
evolved state and the final state. The bound characterizes the state
discrepancy induced by the non-unitary dynamics, and thus reflects the
dissipative nature of irreversibility. Intriguingly, the bound can be
evaluated solely in terms of the initial and final states and the system
Hamiltonian, thereby providing a feasible way to estimate entropy production
without prior knowledge of the underlying coupling structure. This finding
refines the second law of thermodynamics and reveals a universal feature of
thermal relaxation processes.

_Introduction._ —The last two decades have witnessed substantial progress in
the thermodynamics of nonequilibrium systems subject to significant
fluctuations. Various properties of small systems have been elucidated with
the advent of comprehensive frameworks such as stochastic thermodynamics [1,
2] and quantum thermodynamics [3, 4, 5]. One of the prominent universal
relations is the celebrated fluctuation theorem [6, 7, 8, 9, 10, 11], from
which the second law of thermodynamics and the fluctuation-dissipation theorem
can be immediately derived [12, 13, 14]. Beyond the fluctuation theorem, much
recent attention has been focused on thermodynamic uncertainty relations [15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34],
speed limits [35, 36, 37, 38, 39, 40, 41, 42, 43], and refinements of the
second law [44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55]. These findings
are not only theoretically important but also provide powerful tools for
thermodynamic inference, for instance, in the estimation of free energy [56]
and dissipation [57, 58, 59, 60].

Central to most established relations is thermodynamic irreversibility, which
is quantified by irreversible entropy production. The positivity of entropy
production is universally captured by the second law of thermodynamics, which
imposes fundamental limits on the computational cost via Landauer’s principle
[61, 62, 63, 64] and on the performance of physical and biological systems
such as heat engines [65, 66] and molecular motors [67]. The importance of
entropy production has triggered intense research to formulate and investigate
its properties [68, 69, 70, 71, 72], across from classical to quantum (see
Ref. [73] for a review). Nonetheless, with restriction to a specific class of
nonequilibrium processes, rich features of thermodynamic irreversibility may
be found. One of the interesting classes is thermal relaxation, which is
ubiquitous in nature and plays crucial roles in condensed matter [74], heat
engines [75], and quantum state preparation. Any system coupled to thermal
reservoirs unavoidably exchanges energy with the surrounding environment and
relaxes to a stationary state. Of note, Ref. [51] proved that the entropy
production during relaxation of classical Markovian processes is bounded from
below by the classical relative entropy between the initial and final
distributions. For relaxation to equilibrium in open quantum systems, it has
been shown that the entropy production is lower-bounded by a lag between
states in terms of a time-reversed map [48] and a geometrical distance on the
Riemannian manifold [55].

In this Letter, we deepen our understanding of thermodynamic irreversibility
in thermal relaxation processes of open quantum systems. Specifically, we
derive a fundamental bound on irreversibility for systems that are in contact
with thermal reservoirs and described by the Lindblad master equation. We
prove that the irreversible entropy production during relaxation is lower-
bounded by a relative entropy between the final states obtained with the
unitary dynamics and the original dynamics [cf. Eq. (4)]. Lindblad dynamics
comprise unitary and non-unitary parts; therefore, the lower bound quantifies
the state discrepancy induced by the dissipative non-unitary dynamics, which
intuitively reflects the nature of thermodynamic irreversibility (shown in
Fig. 1). Remarkably, the derived bound is saturable, experimentally
accessible, and stronger than the conventional second law of thermodynamics.
Furthermore, the bound provides a feasible way to estimate irreversible
entropy production with the help of the quantum state tomography technique. We
show that a tighter Landauer bound can be obtained as a corollary and
demonstrate our result in an autonomous thermal machine.

_Main result._ —We consider the thermal relaxation process of a Markovian open
quantum system. The system can be simultaneously coupled to multiple thermal
reservoirs at different temperatures. The dynamics of the density matrix
$\rho(t)$ are governed by the Lindblad master equation [76]:

$\partial_{t}\rho(t)=\mathcal{L}[\rho(t)]\coloneqq-i[H,\rho(t)]+\sum_{k}\mathcal{D}_{k}[\rho(t)],$
(1)

where $H$ is the time-independent Hamiltonian and the dissipator is given by
$\mathcal{D}_{k}[\circ]\coloneqq
L_{k}(\circ)L_{k}^{\dagger}-\frac{1}{2}\\{L_{k}^{\dagger}L_{k},(\circ)\\}$.
The jump operators come in pairs $(L_{k},L_{k^{\prime}})$ with energy changes
$(\omega_{k},\omega_{k^{\prime}})$, which satisfy $[L_{k},H]=\omega_{k}L_{k}$
and $\omega_{k}=-\omega_{k^{\prime}}$. This condition implies that the jump
operators account for transitions between different energy eigenbasis with the
same energy change [77, 43]. Note that $[\circ,\star]$ and $\\{\circ,\star\\}$
are, respectively, the commutator and the anticommutator of two operators, and
the Planck constant and the Boltzmann constant are both set to unity
throughout this Letter, $\hbar=k_{\rm B}=1$. We assume the local detailed
balance condition $L_{k}=e^{\Delta s_{\rm
env}^{k}/2}L_{k^{\prime}}^{\dagger}$, which is fulfilled in most cases of
physical interest [71]. Here $\Delta s_{\rm env}^{k}$ is the change in the
environment entropy due to a jump of type $k$. After a sufficiently long time,
the system reaches a stationary state that may no longer be a Gibbs state when
multiple reservoirs are attached. The degree of irreversibility of the
relaxation process during time $\tau$ can be quantified by the irreversible
entropy production $\Sigma_{\tau}$, defined as

$\Sigma_{\tau}\coloneqq\Delta S_{\rm sys}+\Delta S_{\rm env},$ (2)

where $\Delta S_{\rm sys}\coloneqq{\rm
tr}\left\\{\rho(0)\ln\rho(0)\right\\}-{\rm
tr}\left\\{\rho(\tau)\ln\rho(\tau)\right\\}$ is the change in the system
entropy (characterized by the von Neumann entropy) and $\Delta S_{\rm env}$
corresponds to the entropy change of the environment, given by [77]

$\Delta S_{\rm env}\coloneqq\int_{0}^{\tau}\sum_{k}{\rm
tr}\left\\{L_{k}\rho(t)L_{k}^{\dagger}\right\\}\Delta s_{\rm env}^{k}dt.$ (3)

Within this definition, it can be proved that the entropy production is always
nonnegative, $\Sigma_{\tau}\geq 0$ [78].

Figure 1: Geometrical illustration of the main result. The manifold of density
matrices that can be generated from $\rho(0)$ via nondissipative unitary
transforms is denoted by $\mathcal{M}_{\rho(0)}$. The time evolution of the
density matrix under the Lindblad dynamics and the unitary dynamics is
described by the solid line and the dashed line, respectively. The
irreversible entropy production $\Sigma_{\tau}$ is bounded from below by the
information-theoretical distance $S_{\mathbb{M}}[\rho_{u}(\tau)||\rho(\tau)]$
— a relative entropy between the unitarily-evolved state
$\rho_{u}(\tau)\coloneqq U_{\tau}\rho(0)U_{\tau}^{\dagger}$ and the final
state $\rho(\tau)$.

We explain our main result under the given setup. The proof is provided at the
end of the Letter. Our main result is a lower bound on $\Sigma_{\tau}$ in
terms of a relative entropy between the initial and final states,

$\Sigma_{\tau}\geq
S_{\mathbb{M}}[U_{\tau}\rho(0)U_{\tau}^{\dagger}||\rho(\tau)],$ (4)

where $U_{t}\coloneqq e^{-iHt}$ is the unitary operator and
$S_{\mathbb{M}}(\rho||\sigma)\coloneqq S(\rho||\sum_{n}\Pi_{n}\sigma\Pi_{n})$
is the projectively measured relative entropy between $\rho$ and $\sigma$ with
the eigenbasis $\\{\Pi_{n}\\}$ of $\rho$. Here, $S(\rho||\sigma)\coloneqq{\rm
tr}\left\\{\rho(\ln\rho-\ln\sigma)\right\\}\geq 0$ is the quantum relative
entropy between states $\rho$ and $\sigma$. The inequality (4) indicates that
the entropy production is bounded from below by an information-theoretical
distance between the initial and final states, which strengthens the Clausius
inequality in the conventional second law of thermodynamics for thermal
relaxation processes.

Some remarks regarding the main result are in order. First, the bound is
geometrically and intuitively understandable. The system state is governed by
Lindblad dynamics, which consist of a non-dissipative unitary part and a
dissipative non-unitary part. The lower bound is the distance between the
unitarily-evolved state and the final state; therefore, it quantifies how far
the system is driven by non-unitary dynamics, and thereby intuitively reflects
the nature of entropy production, namely a dissipative term. When the system
is uncoupled to the reservoirs and governed by unitary dynamics, both the
entropy production and relative entropy vanish, and the derived relation
becomes a trivial equality. Second, the bound is tight and can be saturated,
for example, in the long-time regime; consequently, it can be applied to
thermodynamic inference. In particular, given the initial and final states and
the system Hamiltonian, a lower bound of entropy production can be estimated
without requisite prior knowledge of the underlying dynamics. Third, the bound
can be interpreted as a quantum speed limit, $\tau\geq
S_{\mathbb{M}}[U_{\tau}\rho(0)U_{\tau}^{\dagger}||\rho(\tau)]/\overline{\Sigma}$,
where $\overline{\Sigma}\coloneqq\Sigma_{\tau}/\tau$ is the average entropy
production rate. An important implication of this speed limit is that a fast
state-transformation requires a high dissipation rate [41, 55]. Last, in the
classical limit (e.g., when the initial density matrix has no coherence in the
energy eigenbasis of the Hamiltonian), the lower bound reduces exactly to the
classical relative entropy between the initial and final distributions;
therefore, our result generalizes the classical bound reported in Ref. [51] to
the case of multiple reservoirs. Note also that the relation (4) is valid even
for systems with broken time-reversal symmetry, such as electronic systems
with a Peierls phase.

A comparison to the existing bounds on entropy production is provided. Some
strong bounds were derived for finite-dimension [62] and zero-temperature [64]
environments. Nonetheless, these bounds reduce to the conventional second law
for either infinitely large or high-temperature environments. Another
information-theoretical bound [48] was derived for thermal relaxation
processes; however, this bound is only applicable to the single-reservoir
case. Our bound thus plays an important role in the regimes in which the
existing bounds either become trivial or are inapplicable.

Figure 2: Numerical illustration of the main result. (a) Schematic diagram of
the two-reservoir machine. (b) The ratio
$S_{\mathbb{M}}[U_{\tau}\rho(0)U_{\tau}^{\dagger}||\rho(\tau)]/\Sigma_{\tau}$
is plotted as a function of time $\tau$, and each solid line depicts the
result obtained with $\kappa$ ranged from $1$ to $4$. Parameters are fixed as
$\omega_{1}=\omega_{3}=0.2$, $\gamma=0.01$, and $\beta_{1}=1$. (c) The ratios
$S_{\mathbb{M}}[U_{\tau}\rho(0)U_{\tau}^{\dagger}||\rho(\tau)]/\Sigma_{\tau}$
(solid line) and $D[p_{n}(0)||p_{n}(\tau)]/\Sigma_{\tau}$ (dash-dotted line)
are plotted with $\kappa$ ranged from $1$ to $4$. Parameters are fixed as
$\omega_{1}=0.2$, $\omega_{3}=0.1$, $\gamma=0.01$, and $\beta_{1}=1$.

As coupled to a single thermal reservoir at the inverse temperature $\beta$,
the system relaxes toward an equilibrium state $\pi\coloneqq e^{-\beta H}/Z$,
irrespective of the initial state. In this case, a Hamiltonian-free lower
bound on the entropy production can be obtained [79],

$\Sigma_{\tau}\geq S_{\mathbb{E}}[\rho(0)||\rho(\tau)],$ (5)

where
$S_{\mathbb{E}}(\rho||\sigma)\coloneqq\sum_{n}a_{n}\ln(a_{n}/b_{n})\eqqcolon
D(a_{n}||b_{n})$ is exactly the classical relative entropy between
distributions $\\{a_{n}\\}$ and $\\{b_{n}\\}$, which are the increasing
eigenvalues of $\rho$ and $\sigma$, respectively. Any unitary transform does
not change the magnitude of the eigenvalues of a density matrix but only the
eigenbasis. Therefore, the term $S_{\mathbb{E}}$ quantitatively characterizes
the state change caused by the non-unitary dynamics. The lower bound is now
dependent only on the initial and final states, which is an inherent feature
of thermal relaxation processes. For generic time-driven systems, it can be
proved that there does not exist such a universal metric that bounds
irreversible entropy production from below [79]. However, for a specific class
of quantum systems, a metric based on the thermodynamic length can be found
[52].

_Tightening Landauer’s principle._ —Information and thermodynamics can be
intuitively related via Landauer’s principle [61], which quantifies the
minimal heat dissipation associated with erasure of information in a memory.
The inequality in Eq. (4) derives a tighter bound than the conventional
Landauer bound $\Delta S_{\rm env}\geq-\Delta S_{\rm sys}$. Consider the
scenario in which a qubit is reset from a maximally mixed state $\mathbb{I}/2$
to the ground state $|0\rangle\langle 0|$ by quenching the Hamiltonian and
letting the system relax to the stationary state. It should be stressed that
the final state cannot be exactly $|0\rangle\langle 0|$ in a finite time. Let
$\delta\in(0,1)$ be the probability that the qubit is in the ground state at
time $\tau$, i.e., $\delta=\langle 0|\rho(\tau)|0\rangle$. According to Eq.
(4), the minimal heat dissipation is related to the probability of success as

$\Delta S_{\rm env}\geq-\Delta S_{\rm sys}-\frac{1}{2}\ln[4\delta(1-\delta)].$
(6)

Equation (6) implies that the higher precision of a memory is, the more heat
is dissipated. As $\delta\to 1$, the term in the right-hand side of Eq. (6)
goes to infinity.

_Examples._ —To demonstrate the main result [Eq. (4)], we consider an
autonomous thermal machine [77] with three levels
$\\{|\epsilon_{g}\rangle,|\epsilon_{A}\rangle,|\epsilon_{B}\rangle\\}$. Such
machines can operate as refrigerators and are also the building blocks for
quantum clocks [80, 81]. The Hamiltonian of the system is
$H=\omega_{1}|\epsilon_{A}\rangle\langle\epsilon_{A}|+\omega_{2}|\epsilon_{B}\rangle\langle\epsilon_{B}|$,
where $\omega_{1}$, $\omega_{2}$, and
$\omega_{3}\coloneqq\omega_{2}-\omega_{1}$ are frequency gaps between
$|\epsilon_{g}\rangle\leftrightarrow|\epsilon_{A}\rangle$,
$|\epsilon_{g}\rangle\leftrightarrow|\epsilon_{B}\rangle$, and
$|\epsilon_{A}\rangle\leftrightarrow|\epsilon_{B}\rangle$, respectively. The
machine is powered by two reservoirs at different inverse temperatures
$\beta_{1}\geq\beta_{2}$, which mediate transitions between the energy levels
[see Fig. 2(a)].

First, we examine the case in which $\omega_{1}=\omega_{3}$ and the Lindblad
equation has four jump operators,
$L_{1}=\sqrt{\eta_{1}}(|\epsilon_{A}\rangle\langle\epsilon_{g}|+|\epsilon_{B}\rangle\langle\epsilon_{A}|)$,
$L_{1^{\prime}}=\sqrt{\eta_{1^{\prime}}}(|\epsilon_{g}\rangle\langle\epsilon_{A}|+|\epsilon_{A}\rangle\langle\epsilon_{B}|)$,
$L_{2}=\sqrt{\eta_{2}}|\epsilon_{B}\rangle\langle\epsilon_{g}|$, and
$L_{2^{\prime}}=\sqrt{\eta_{2^{\prime}}}|\epsilon_{g}\rangle\langle\epsilon_{B}|$,
where $\eta_{1}=\gamma n_{1}^{\rm th}(\omega_{1})$,
$\eta_{1^{\prime}}=\gamma[n_{1}^{\rm th}(\omega_{1})+1]$, $\eta_{2}=\gamma
n_{2}^{\rm th}(\omega_{2})$, and $\eta_{2^{\prime}}=\gamma[n_{2}^{\rm
th}(\omega_{2})+1]$. Here, $n_{r}^{\rm
th}(\omega)\coloneqq(e^{\beta_{r}\omega}-1)^{-1}$ denotes the Planck
distribution and $\gamma$ is the decay rate. Let $\pi^{\rm ss}$ be the
stationary state of the system. We set $\beta_{1}=\kappa\beta_{2}$ with
$\kappa\geq 1$, and the initial density matrix is a pure state
$\rho(0)=|\varphi\rangle\langle\varphi|$, where
$|\varphi\rangle=\sqrt{10-\kappa}|\epsilon_{g}\rangle/3+\sqrt{\kappa-1}|\epsilon_{B}\rangle/3$.
The magnitude of $\kappa$ characterizes the coherence in the initial state and
the nonequilibrium degree of $\pi^{\rm ss}$. When $\kappa=1$, $\rho(0)$ is
diagonal in the energy levels, and the system relaxes to the equilibrium Gibbs
state. With $\kappa>1$, coherence emerges in the initial state, and $\pi^{\rm
ss}$ becomes a nonequilibrium steady state. $\kappa$ is varied from $1$ to $4$
and the ratio $S_{\mathbb{M}}/\Sigma_{\tau}$ is plotted as a function of time
$\tau$ in Fig. 2(b). As can be seen, the bound is tight and can be saturated
for a long time. Note that the entropy production rate is always positive for
$\kappa>1$; therefore, $S_{\mathbb{M}}/\Sigma_{\tau}$ goes to zero in the
long-time limit. However, the relation (4) is useful because it shows a
meaningful bound for initial rapid relaxation processes.

Next, to compare our result with a classical bound, we consider the case that
each jump operator characterizes a single jump between two energy levels,
$L_{mn}=\sqrt{\eta_{mn}}|\epsilon_{m}\rangle\langle\epsilon_{n}|~{}(m\neq n)$.
The transition rates are $\eta_{Ag}=\gamma n_{1}^{\rm th}(\omega_{1})$,
$\eta_{gA}=\gamma[n_{1}^{\rm th}(\omega_{1})+1]$, $\eta_{BA}=\gamma n_{1}^{\rm
th}(\omega_{3})$, $\eta_{AB}=\gamma[n_{1}^{\rm th}(\omega_{3})+1]$,
$\eta_{Bg}=\gamma n_{2}^{\rm th}(\omega_{2})$, and
$\eta_{gB}=\gamma[n_{2}^{\rm th}(\omega_{2})+1]$. In this case, the time
evolution of the diagonal terms
$p_{n}(t)\coloneqq\langle\epsilon_{n}|\rho(t)|\epsilon_{n}\rangle$ follows a
classical master equation with time-independent transition rates [82].
Thereby, Eq. (4) is applied to the diagonal dynamics, which gives
$\Sigma_{\tau}^{\rm cl}\geq D[p_{n}(0)||p_{n}(\tau)]$, where
$\Sigma_{\tau}^{\rm cl}$ is the entropy production associated with the
classical master equation. In the long-time regime (i.e., when coherence in
$\rho(\tau)$ vanishes), it can be proved that
$\Sigma_{\tau}\geq\Sigma_{\tau}^{\rm cl}$; consequently, $\Sigma_{\tau}\geq
D[p_{n}(0)||p_{n}(\tau)]$, which is referred to as the classical bound. The
temperatures and the initial state are the same as in the previous case.
Analogously, $\kappa$ is varied from $1$ to $4$ and the ratios
$S_{\mathbb{M}}/\Sigma_{\tau}$ and $D/\Sigma_{\tau}$ are plotted as functions
of time $\tau$ in Fig. 2(c). Two bounds coincide when $\kappa=1$ because there
is no coherence in $\rho(t)$ for all $t$. However, as $\kappa$ increases, the
bound $S_{\mathbb{M}}$ is tighter than the classical bound. This is because
our bound captures the coherence contribution in the initial state, whereas
the classical bound does not.

_Proof of Eq. ( 4)._—We first rewrite the dynamics of the density matrix
$\rho(t)$ in the interaction picture. Define $\rho_{I}(t)\coloneqq
U_{t}^{\dagger}\rho(t)U_{t}$, the time evolution of $\rho_{I}(t)$ obeys the
equation [79]

$\partial_{t}\rho_{I}(t)=\sum_{k}\mathcal{D}_{k}[\rho_{I}(t)],$ (7)

with the initial condition $\rho_{I}(0)=\rho(0)$. Our approach is based on
unraveling the dynamics described by Eq. (7) in terms of quantum trajectories.
In what follows, we demonstrate that the irreversible entropy production
$\Sigma_{\tau}$ can be mathematically linked to the level of individual
trajectories.

The framework of quantum trajectories [83, 84] was originally developed in the
field of quantum optics as a means to numerically simulate open quantum
systems [82]. Within this approach, the master equation is unraveled into
stochastic time evolutions of the pure state of the system $|\psi(t)\rangle$,
conditioned on measurement outcomes obtained from continuous monitoring of the
environment. Each individual trajectory of a stochastic realization can be
described by a smooth evolution with discontinuous changes caused by quantum
jumps in the state at random times. A quantum jump is associated with the
detection of an event in the environment (e.g., emission or absorption of
photons). The time evolution of the pure state can be described by the
stochastic Schrödinger equation [82]:

$\displaystyle d|\psi(t)\rangle$
$\displaystyle=\mathcal{S}[|\psi(t)\rangle]dt$ (8) $\displaystyle\hskip
9.95863pt+\sum_{k}\left(\frac{L_{k}|\psi(t)\rangle}{\sqrt{\langle
L_{k}^{\dagger}L_{k}\rangle_{\psi(t)}}}-|\psi(t)\rangle\right)dN_{k}(t),$

where $\mathcal{S}(|\psi\rangle)\coloneqq(1/2)\sum_{k}(\langle
L_{k}^{\dagger}L_{k}\rangle_{\psi}-L_{k}^{\dagger}L_{k})|\psi\rangle$ and
$\langle A\rangle_{\psi}\coloneqq\langle\psi|A|\psi\rangle$. The stochastic
increment $dN_{k}(t)$ is either $0$ or $1$ (when a jump of type $k$ is
detected), and its ensemble average at time $t$ is
$\mathbbmss{E}[dN_{k}(t)]=\langle L_{k}^{\dagger}L_{k}\rangle_{\psi(t)}dt$.
Under appropriate initial conditions, the average of
$|\psi(t)\rangle\langle\psi(t)|$ over all possible trajectories reduces
exactly to the density matrix in the interaction picture,
$\mathbbmss{E}[|\psi(t)\rangle\langle\psi(t)|]=\rho_{I}(t)$.

Now we define the stochastic entropy production on a single trajectory. We
employ a two-point measurement scheme on the system, where projective
measurements are performed at the beginning and at the end of any single
trajectory [71]. Let $\rho_{I}(0)=\sum_{n}p_{n}|n\rangle\langle n|$ and
$\rho_{I}(\tau)=\sum_{m}p_{m}|m\rangle\langle m|$ be the spectral
decompositions of $\rho_{I}(0)$ and $\rho_{I}(\tau)$, the forward process is
operated as follows. The state $|\psi(0)\rangle$ is sampled from the ensemble
$\\{|n\rangle\\}$ with probabilities $\\{p_{n}\\}$. The selected state is
confirmed by the first measurement in the $\\{|n\rangle\\}$ eigenbasis at time
$t=0$. The pure state then evolves in time according to Eq. (8), and the
second measurement in the $\\{|m\rangle\\}$ eigenbasis is executed at time
$t=\tau$. This procedure results in a stochastic trajectory
$\Gamma=\\{n,(k_{1},t_{1}),\dots,(k_{J},t_{J}),m\\}$, where $n$ and $m$ are
measurement outcomes of the first and second measurements, respectively, and
$(k_{j},t_{j})$ denotes a jump of type $k_{j}$ that occurs at time $t_{j}$
($j=1,\dots,J$ and $0\leq t_{1}\leq\dots\leq t_{J}\leq\tau$). To define the
time-reversed (backward) process, the antiunitary time-reversal operator
$\Theta$ is introduced, which satisfies $\Theta i=-i\Theta$ and
$\Theta\Theta^{\dagger}=\Theta^{\dagger}\Theta=\mathbb{I}$. This operator
changes the sign of odd variables under time reversal, such as angular
momentum or magnetic fields [11]. In the backward process, the initial state
$|\tilde{\psi}(0)\rangle$ is sampled from the ensemble
$\\{|\tilde{m}\rangle=\Theta|m\rangle\\}$ with probabilities $\\{p_{m}\\}$ and
is verified with the projective measurement in the $\\{|\tilde{m}\rangle\\}$
eigenbasis. The pure state $|\tilde{\psi}(t)\rangle$ analogously obeys Eq.
(8), in which the jump operators are replaced by the time-reversed
counterparts [77]

$\tilde{L}_{k}=e^{-\Delta s_{\rm env}^{k}/2}\Theta
L_{k}^{\dagger}\Theta^{\dagger}=\Theta L_{k^{\prime}}\Theta^{\dagger}.$ (9)

At time $t=\tau$, the second projective measurement in the
$\\{|\tilde{n}\rangle=\Theta|n\rangle\\}$ eigenbasis is performed. Let
$\tilde{\Gamma}=\\{m,(k_{J},\tau-t_{J}),\dots,(k_{1},\tau-t_{1}),n\\}$ be the
time-reversed trajectory that corresponds to $\Gamma$, and the stochastic
entropy production associated with the trajectory $\Gamma$ is defined as

$\Delta s_{\rm
tot}[\Gamma]\coloneqq\ln\frac{P(\Gamma)}{\tilde{P}(\tilde{\Gamma})}=\ln\frac{p_{n}}{p_{m}}+\sum_{j=1}^{J}\Delta
s_{\rm env}^{k_{j}},$ (10)

where $P(\Gamma)$ and $\tilde{P}(\tilde{\Gamma})$ are the probabilities of
observing the trajectories $\Gamma$ and $\tilde{\Gamma}$, respectively [85].
Notably, we can prove that the average of $\Delta s_{\rm tot}$ is exactly the
irreversible entropy production of the original dynamics [Eq. (1)] [79],

$\Sigma_{\tau}=\langle\Delta s_{\rm
tot}[\Gamma]\rangle=D[P(\Gamma)||\tilde{P}(\tilde{\Gamma})].$ (11)

Note that the classical relative entropy monotonically decreases under
information processing. Applying the coarse-graining operation
$\Lambda:~{}\Gamma\mapsto n$, which leaves only the first measurement outcome,
to $D[P(\Gamma)||\tilde{P}(\tilde{\Gamma})]$, we obtain a lower bound on the
entropy production from Eq. (11) as

$\Sigma_{\tau}\geq D(p_{n}||\tilde{p}_{n}),$ (12)

where $\tilde{p}_{n}$ is the probability to observe the measurement outcome
$|\tilde{n}\rangle$ at the end of the backward process [86]. It is crucial to
note from Eq. (9) that the (inverted) jump operators in the backward process
are identical with those in the forward process. As a consequence, the density
matrix in the backward process immediately before the second projective
measurement is performed can be explicitly expressed as
$\tilde{\rho}_{I}(\tau)=\Theta\rho_{I}(2\tau)\Theta^{\dagger}$. The
probability distribution $\tilde{p}_{n}$ can be calculated as
$\tilde{p}_{n}=\langle\tilde{n}|\tilde{\rho}_{I}(\tau)|\tilde{n}\rangle=\langle
n|U_{2\tau}^{\dagger}\rho(2\tau)U_{2\tau}|n\rangle$. The inequality (12) holds
for an arbitrary time $\tau>0$ and the entropy production increases in time
(i.e., $\Sigma_{\tau}\geq\Sigma_{\tau/2}$); therefore, Eq. (4) is immediately
obtained.

_Conclusion._ —In this Letter, we derived the fundamental bound on
irreversibility for thermal relaxation processes of Markovian open quantum
systems. The bound refines the second law of thermodynamics and can be
evaluated without knowing details of the underlying dynamics; therefore, it is
applicable to the estimation of irreversible entropy production. Since thermal
relaxation is the basis for heat engines, the result of this study is expected
to lay the foundations to obtain useful thermodynamic bounds on relevant
physical quantities such as power and efficiency [87].

###### Acknowledgements.

The authors acknowledge Keiji Saito, Francesco Buscemi, and Valerio Scarani
for fruitful discussions. The authors are greatly grateful to Keiji Saito for
the careful reading of the manuscript and for invaluable comments. This work
was supported by Ministry of Education, Culture, Sports, Science and
Technology (MEXT) KAKENHI Grant No. JP19K12153.

## References

  * Sekimoto [2010] K. Sekimoto,  _Stochastic Energetics_ , Vol. 799 (Springer, Berlin, 2010).
  * Seifert [2012] U. Seifert, Stochastic thermodynamics, fluctuation theorems and molecular machines, Rep. Prog. Phys. 75, 126001 (2012).
  * Vinjanampathy and Anders [2016] S. Vinjanampathy and J. Anders, Quantum thermodynamics, Contemp. Phys. 57, 545 (2016).
  * Goold  _et al._ [2016] J. Goold, M. Huber, A. Riera, L. del Rio, and P. Skrzypczyk, The role of quantum information in thermodynamics—a topical review, J. Phys. A 49, 143001 (2016).
  * Deffner and Campbell [2019] S. Deffner and S. Campbell,  _Quantum Thermodynamics_ (Morgan & Claypool Publishers, San Rafael, 2019).
  * Evans  _et al._ [1993] D. J. Evans, E. G. D. Cohen, and G. P. Morriss, Probability of second law violations in shearing steady states, Phys. Rev. Lett. 71, 2401 (1993).
  * Gallavotti and Cohen [1995] G. Gallavotti and E. G. D. Cohen, Dynamical ensembles in nonequilibrium statistical mechanics, Phys. Rev. Lett. 74, 2694 (1995).
  * Crooks [1999] G. E. Crooks, Entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences, Phys. Rev. E 60, 2721 (1999).
  * Jarzynski [2000] C. Jarzynski, Hamiltonian derivation of a detailed fluctuation theorem, J. Stat. Phys. 98, 77 (2000).
  * Esposito  _et al._ [2009] M. Esposito, U. Harbola, and S. Mukamel, Nonequilibrium fluctuations, fluctuation theorems, and counting statistics in quantum systems, Rev. Mod. Phys. 81, 1665 (2009).
  * Campisi  _et al._ [2011] M. Campisi, P. Hänggi, and P. Talkner, Colloquium: Quantum fluctuation relations: Foundations and applications, Rev. Mod. Phys. 83, 771 (2011).
  * Gallavotti [1996] G. Gallavotti, Extension of Onsager’s reciprocity to large fields and the chaotic hypothesis, Phys. Rev. Lett. 77, 4334 (1996).
  * Andrieux and Gaspard [2007] D. Andrieux and P. Gaspard, A fluctuation theorem for currents and non-linear response coefficients, J. Stat. Mech.: Theory Exp. 2007, P02006.
  * Saito and Utsumi [2008] K. Saito and Y. Utsumi, Symmetry in full counting statistics, fluctuation theorem, and relations among nonlinear transport coefficients in the presence of a magnetic field, Phys. Rev. B 78, 115429 (2008).
  * Barato and Seifert [2015] A. C. Barato and U. Seifert, Thermodynamic uncertainty relation for biomolecular processes, Phys. Rev. Lett. 114, 158101 (2015).
  * Gingrich  _et al._ [2016] T. R. Gingrich, J. M. Horowitz, N. Perunov, and J. L. England, Dissipation bounds all steady-state current fluctuations, Phys. Rev. Lett. 116, 120601 (2016).
  * Horowitz and Gingrich [2017] J. M. Horowitz and T. R. Gingrich, Proof of the finite-time thermodynamic uncertainty relation for steady-state currents, Phys. Rev. E 96, 020103(R) (2017).
  * Proesmans and den Broeck [2017] K. Proesmans and C. V. den Broeck, Discrete-time thermodynamic uncertainty relation, Europhys. Lett. 119, 20001 (2017).
  * Brandner  _et al._ [2018] K. Brandner, T. Hanazato, and K. Saito, Thermodynamic bounds on precision in ballistic multiterminal transport, Phys. Rev. Lett. 120, 090601 (2018).
  * Hasegawa and Van Vu [2019a] Y. Hasegawa and T. Van Vu, Uncertainty relations in stochastic processes: An information inequality approach, Phys. Rev. E 99, 062126 (2019a).
  * Van Vu and Hasegawa [2019] T. Van Vu and Y. Hasegawa, Uncertainty relations for underdamped Langevin dynamics, Phys. Rev. E 100, 032130 (2019).
  * Hasegawa and Van Vu [2019b] Y. Hasegawa and T. Van Vu, Fluctuation theorem uncertainty relation, Phys. Rev. Lett. 123, 110602 (2019b).
  * Timpanaro  _et al._ [2019] A. M. Timpanaro, G. Guarnieri, J. Goold, and G. T. Landi, Thermodynamic uncertainty relations from exchange fluctuation theorems, Phys. Rev. Lett. 123, 090604 (2019).
  * Guarnieri  _et al._ [2019] G. Guarnieri, G. T. Landi, S. R. Clark, and J. Goold, Thermodynamics of precision in quantum nonequilibrium steady states, Phys. Rev. Research 1, 033021 (2019).
  * Carollo  _et al._ [2019] F. Carollo, R. L. Jack, and J. P. Garrahan, Unraveling the large deviation statistics of Markovian open quantum systems, Phys. Rev. Lett. 122, 130605 (2019).
  * Vo  _et al._ [2020] V. T. Vo, T. Van Vu, and Y. Hasegawa, Unified approach to classical speed limit and thermodynamic uncertainty relation, Phys. Rev. E 102, 062132 (2020).
  * Dechant and Sasa [2020] A. Dechant and S.-i. Sasa, Fluctuation-response inequality out of equilibrium, Proc. Natl. Acad. Sci. U.S.A. 117, 6430 (2020).
  * Hasegawa [2020] Y. Hasegawa, Quantum thermodynamic uncertainty relation for continuous measurement, Phys. Rev. Lett. 125, 050601 (2020).
  * Van Vu and Hasegawa [2020] T. Van Vu and Y. Hasegawa, Thermodynamic uncertainty relations under arbitrary control protocols, Phys. Rev. Research 2, 013060 (2020).
  * Koyuk and Seifert [2020] T. Koyuk and U. Seifert, Thermodynamic uncertainty relation for time-dependent driving, Phys. Rev. Lett. 125, 260604 (2020).
  * Miller  _et al._ [2021] H. J. D. Miller, M. H. Mohammady, M. Perarnau-Llobet, and G. Guarnieri, Thermodynamic uncertainty relation in slowly driven quantum heat engines, Phys. Rev. Lett. 126, 210603 (2021).
  * Hasegawa [2021] Y. Hasegawa, Thermodynamic uncertainty relation for general open quantum systems, Phys. Rev. Lett. 126, 010602 (2021).
  * Sacchi [2021] M. F. Sacchi, Thermodynamic uncertainty relations for bosonic Otto engines, Phys. Rev. E 103, 012111 (2021).
  * Horowitz and Gingrich [2020] J. M. Horowitz and T. R. Gingrich, Thermodynamic uncertainty relations constrain non-equilibrium fluctuations, Nat. Phys. 16, 15 (2020).
  * Mandelstam and Tamm [1945] L. Mandelstam and I. Tamm, The uncertainty relation between energy and time in non-relativistic quantum mechanics, J. Phys. USSR 9, 249 (1945).
  * Margolus and Levitin [1998] N. Margolus and L. B. Levitin, The maximum speed of dynamical evolution, Physica D 120, 188 (1998).
  * del Campo  _et al._ [2013] A. del Campo, I. L. Egusquiza, M. B. Plenio, and S. F. Huelga, Quantum speed limits in open system dynamics, Phys. Rev. Lett. 110, 050403 (2013).
  * Pires  _et al._ [2016] D. P. Pires, M. Cianciaruso, L. C. Céleri, G. Adesso, and D. O. Soares-Pinto, Generalized geometric quantum speed limits, Phys. Rev. X 6, 021031 (2016).
  * Deffner and Campbell [2017] S. Deffner and S. Campbell, Quantum speed limits: from Heisenberg’s uncertainty principle to optimal quantum control, J. Phys. A 50, 453001 (2017).
  * Okuyama and Ohzeki [2018] M. Okuyama and M. Ohzeki, Quantum speed limit is not quantum, Phys. Rev. Lett. 120, 070402 (2018).
  * Shiraishi  _et al._ [2018] N. Shiraishi, K. Funo, and K. Saito, Speed limit for classical stochastic processes, Phys. Rev. Lett. 121, 070601 (2018).
  * Shanahan  _et al._ [2018] B. Shanahan, A. Chenu, N. Margolus, and A. del Campo, Quantum speed limits across the quantum-to-classical transition, Phys. Rev. Lett. 120, 070401 (2018).
  * Funo  _et al._ [2019] K. Funo, N. Shiraishi, and K. Saito, Speed limit for open quantum systems, New J. Phys. 21, 013006 (2019).
  * Gomez-Marin  _et al._ [2008] A. Gomez-Marin, J. M. R. Parrondo, and C. Van den Broeck, Lower bounds on dissipation upon coarse graining, Phys. Rev. E 78, 011107 (2008).
  * Vaikuntanathan and Jarzynski [2009] S. Vaikuntanathan and C. Jarzynski, Dissipation and lag in irreversible processes, Europhys. Lett. 87, 60005 (2009).
  * Deffner and Lutz [2010] S. Deffner and E. Lutz, Generalized Clausius inequality for nonequilibrium quantum processes, Phys. Rev. Lett. 105, 170402 (2010).
  * Aurell  _et al._ [2011] E. Aurell, C. Mejía-Monasterio, and P. Muratore-Ginanneschi, Optimal protocols and optimal transport in stochastic thermodynamics, Phys. Rev. Lett. 106, 250601 (2011).
  * Alhambra and Woods [2017] A. M. Alhambra and M. P. Woods, Dynamical maps, quantum detailed balance, and the Petz recovery map, Phys. Rev. A 96, 022118 (2017).
  * Mancino  _et al._ [2018] L. Mancino, V. Cavina, A. De Pasquale, M. Sbroscia, R. I. Booth, E. Roccia, I. Gianani, V. Giovannetti, and M. Barbieri, Geometrical bounds on irreversibility in open quantum systems, Phys. Rev. Lett. 121, 160602 (2018).
  * Dechant and Sakurai [2019] A. Dechant and Y. Sakurai, Thermodynamic interpretation of Wasserstein distance, arXiv preprint arXiv:1912.08405 (2019).
  * Shiraishi and Saito [2019] N. Shiraishi and K. Saito, Information-theoretical bound of the irreversibility in thermal relaxation processes, Phys. Rev. Lett. 123, 110603 (2019).
  * Abiuso  _et al._ [2020] P. Abiuso, H. J. D. Miller, M. Perarnau-Llobet, and M. Scandi, Geometric optimisation of quantum thermodynamic processes, Entropy 22, 1076 (2020).
  * Buscemi  _et al._ [2020] F. Buscemi, D. Fujiwara, N. Mitsui, and M. Rotondo, Thermodynamic reverse bounds for general open quantum processes, Phys. Rev. A 102, 032210 (2020).
  * Campisi and Buffoni [2021] M. Campisi and L. Buffoni, Improved bound on entropy production in a quantum annealer, Phys. Rev. E 104, L022102 (2021).
  * Van Vu and Hasegawa [2021] T. Van Vu and Y. Hasegawa, Geometrical bounds of the irreversibility in Markovian systems, Phys. Rev. Lett. 126, 010601 (2021).
  * Gore  _et al._ [2003] J. Gore, F. Ritort, and C. Bustamante, Bias and error in estimates of equilibrium free-energy differences from nonequilibrium measurements, Proc. Natl. Acad. Sci. U.S.A. 100, 12564 (2003).
  * Li  _et al._ [2019] J. Li, J. M. Horowitz, T. R. Gingrich, and N. Fakhri, Quantifying dissipation using fluctuating currents, Nat. Commun. 10, 1666 (2019).
  * Manikandan  _et al._ [2020] S. K. Manikandan, D. Gupta, and S. Krishnamurthy, Inferring entropy production from short experiments, Phys. Rev. Lett. 124, 120603 (2020).
  * Van Vu  _et al._ [2020] T. Van Vu, V. T. Vo, and Y. Hasegawa, Entropy production estimation with optimal current, Phys. Rev. E 101, 042138 (2020).
  * Otsubo  _et al._ [2020] S. Otsubo, S. Ito, A. Dechant, and T. Sagawa, Estimating entropy production by machine learning of short-time fluctuating currents, Phys. Rev. E 101, 062106 (2020).
  * Landauer [1961] R. Landauer, Irreversibility and heat generation in the computing process, IBM J. Res. Dev. 5, 183 (1961).
  * Reeb and Wolf [2014] D. Reeb and M. M. Wolf, An improved Landauer principle with finite-size corrections, New J. Phys. 16, 103011 (2014).
  * Goold  _et al._ [2015] J. Goold, M. Paternostro, and K. Modi, Nonequilibrium quantum Landauer principle, Phys. Rev. Lett. 114, 060602 (2015).
  * Timpanaro  _et al._ [2020] A. M. Timpanaro, J. P. Santos, and G. T. Landi, Landauer’s principle at zero temperature, Phys. Rev. Lett. 124, 240601 (2020).
  * Shiraishi  _et al._ [2016] N. Shiraishi, K. Saito, and H. Tasaki, Universal trade-off relation between power and efficiency for heat engines, Phys. Rev. Lett. 117, 190601 (2016).
  * Pietzonka and Seifert [2018] P. Pietzonka and U. Seifert, Universal trade-off between power, efficiency, and constancy in steady-state heat engines, Phys. Rev. Lett. 120, 190602 (2018).
  * Pietzonka  _et al._ [2016] P. Pietzonka, A. C. Barato, and U. Seifert, Universal bound on the efficiency of molecular motors, J. Stat. Mech.: Theory Exp. 2016, 124004.
  * Saito and Dhar [2016] K. Saito and A. Dhar, Waiting for rare entropic fluctuations, Europhys. Lett. 114, 50004 (2016).
  * Neri  _et al._ [2017] I. Neri, E. Roldán, and F. Jülicher, Statistics of infima and stopping times of entropy production and applications to active molecular processes, Phys. Rev. X 7, 011019 (2017).
  * Pigolotti  _et al._ [2017] S. Pigolotti, I. Neri, E. Roldán, and F. Jülicher, Generic properties of stochastic entropy production, Phys. Rev. Lett. 119, 140604 (2017).
  * Manzano  _et al._ [2019] G. Manzano, R. Fazio, and E. Roldán, Quantum martingale theory and entropy production, Phys. Rev. Lett. 122, 220602 (2019).
  * Falasco and Esposito [2020] G. Falasco and M. Esposito, Dissipation-time uncertainty relation, Phys. Rev. Lett. 125, 120604 (2020).
  * Landi and Paternostro [2021] G. T. Landi and M. Paternostro, Irreversible entropy production: From classical to quantum, Rev. Mod. Phys. 93, 035008 (2021).
  * Dattagupta [2012] S. Dattagupta,  _Relaxation Phenomena in Condensed Matter Physics_ (Elsevier, New York, 2012).
  * Benenti  _et al._ [2017] G. Benenti, G. Casati, K. Saito, and R. S. Whitney, Fundamental aspects of steady-state conversion of heat to work at the nanoscale, Phys. Rep. 694, 1 (2017).
  * Lindblad [1976] G. Lindblad, On the generators of quantum dynamical semigroups, Commun. Math. Phys. 48, 119 (1976).
  * Manzano  _et al._ [2018] G. Manzano, J. M. Horowitz, and J. M. R. Parrondo, Quantum fluctuation theorems for arbitrary environments: Adiabatic and nonadiabatic entropy production, Phys. Rev. X 8, 031037 (2018).
  * Trushechkin [2019] A. S. Trushechkin, On the general definition of the production of entropy in open Markov quantum systems, J. Math. Sci. 241, 191 (2019).
  * [79] See Supplemental Material at [URL] for details of calculations, which includes Ref. [88].
  * Erker  _et al._ [2017] P. Erker, M. T. Mitchison, R. Silva, M. P. Woods, N. Brunner, and M. Huber, Autonomous quantum clocks: Does thermodynamics limit our ability to measure time?, Phys. Rev. X 7, 031022 (2017).
  * Mitchison [2019] M. T. Mitchison, Quantum thermal absorption machines: refrigerators, engines and clocks, Contemp. Phys. 60, 164 (2019).
  * Breuer and Petruccione [2002] H.-P. Breuer and F. Petruccione,  _The Theory of Open Quantum Systems_ (Oxford University Press, New York, 2002).
  * Horowitz [2012] J. M. Horowitz, Quantum-trajectory approach to the stochastic thermodynamics of a forced harmonic oscillator, Phys. Rev. E 85, 031110 (2012).
  * Horowitz and Parrondo [2013] J. M. Horowitz and J. M. R. Parrondo, Entropy production along nonequilibrium quantum jump trajectories, New J. Phys. 15, 085028 (2013).
  * fnt [a] The first term in the right-hand side of Eq. (10) represents the stochastic change in the von Neumann entropy, whereas the second term corresponds to the stochastic entropy production of the reservoirs.
  * fnt [b] Equation (12) can also be derived using an integral fluctuation theorem [79].
  * Brandner and Saito [2020] K. Brandner and K. Saito, Thermodynamic geometry of microscopic heat engines, Phys. Rev. Lett. 124, 040602 (2020).
  * Zhang  _et al._ [2020] J. W. Zhang, K. Rehan, M. Li, J. C. Li, L. Chen, S.-L. Su, L.-L. Yan, F. Zhou, and M. Feng, Single-atom verification of the information-theoretical bound of irreversibility at the quantum level, Phys. Rev. Research 2, 033082 (2020).


the packing to place these boxes.
We consider three options to place them. The first choice depends on the
widest tall items that intersects the line at $\nicefrac{{1}}{{2}}H$. We fix
their position and attempt to place these extra boxes atop these tall items if
their width is large enough. If this is not possible, we know that the tall
items intersecting $\nicefrac{{1}}{{2}}H$ are not very wide. This allows us to
attempt to place the extra boxes inside the boxes $B$ of height
$0pt(B)>\nicefrac{{3}}{{4}}H$. Again, the feasibility of this placement
depends on the total width of these boxes. Finally, if all else fails, we
place them on top of boxes with height between $\nicefrac{{1}}{{2}}H$ and
$\nicefrac{{3}}{{4}}H$.
The second part of this proof is to show that tall and medium boxes have to
start and end at grid lines. Since we already know from our rounding, Lemma 3,
that tall items start and end at multiples of $\varepsilon^{2}\mathrm{OPT}$,
we can choose these lines as the grid. Setting the start- and endpoints of the
tall and medium boxes to these lines leads to a negligible loss in
approximation ratio as we show in the following.
After placing the boxes on the grid as such, we have fulfilled the
requirements to utilize the reordering techniques from Lemma 6, Lemma 7 and
Lemma 9 to reorder items inside the boxes $\mathcal{B}_{T\cup V}$. After this
reordering, we analyze the number of containers constructed for vertical items
and find a place for the additional containers we need to generate through
Lemma 10. Finally, we show how to place the boxes for horizontal and small
items.
_Step 1: Fixing the position of the widest tall items intersecting $H/2$._ We
begin by inspecting the $1/(\delta^{2}\varepsilon)$ widest tall items crossing
the horizontal line at $\nicefrac{{1}}{{2}}H$. We refer to this set of items
as $T_{\nicefrac{{1}}{{2}}H}$. Each item in this set defines a new immovable
item. Any box that contains this item gets split into three parts. The part to
the left, the part to the right and the part containing the item. The parts to
the left and right are reordered as any other box. The part that contains it
is reordered differently. Since we have a tall item intersecting the
horizontal line at $\nicefrac{{1}}{{2}}H$, the parts above and below this item
can have a height of at most $\nicefrac{{1}}{{2}}H$. We define both of these
parts as new boxes. Thus, we can reorder both of these boxes using Lemma 6.
These reorderings both generate at most $\mathcal{O}(N)$ sub-boxes for tall
and vertical items. This less than the number of boxes generated for a box of
height greater than $\nicefrac{{3}}{{4}}H$. Therefore, we can count this as a
single box of height greater than $\nicefrac{{3}}{{4}}H$ when calculating the
number of added boxes and assume it to be at most $2/(\delta^{2}\varepsilon)$.
After this step, the total number of boxes containing both tall and vertical
items is bounded by $\mathcal{O}(1/(\delta^{2}\varepsilon))$. Furthermore, the
number of vertical lines at box borders through the strip is bounded by the
same amount, namely $\mathcal{O}(1/(\delta^{2}\varepsilon))$.
_Ensuring the alignment of tall and medium boxes to the grid-lines._ In both
Lemma 7 and Lemma 9 we assume that each box with height larger than
$\nicefrac{{1}}{{2}}H$ starts and ends at grid points. We generate this
property here. We define grid lines as integral multiples of
$\varepsilon^{2}\mathrm{OPT}$. Let $B$ be a box with
$0pt(B)>\nicefrac{{1}}{{2}}H$. Inspect the horizontal line $\ell$ at the
smallest multiple of $\varepsilon^{2}\mathrm{OPT}$ in the box $B$. The
distance between $\ell$ and the bottom border clearly has to be smaller than
$\varepsilon^{2}\mathrm{OPT}$. Now, we remove all vertical items below $\ell$
and each item cut by $\ell$ and place them inside an extra box. We know that
each item with height larger than $\varepsilon\mathrm{OPT}$ already starts and
ends at a multiple of $\varepsilon^{2}\mathrm{OPT}$ due to our rounding, Lemma
3, all items we placed inside this extra box have a height less than
$\varepsilon\mathrm{OPT}$. We generate another box in the same manner at the
top of $B$, and repeat this procedure for every other box. This leaves us with
two boxes of height less than $\varepsilon\mathrm{OPT}$ for each box of height
greater than $\nicefrac{{1}}{{2}}H$. Since no two boxes of height greater than
$\nicefrac{{1}}{{2}}H$ can overlap, the total width of these newly generated
boxes is at most $2W$. Therefore, we can place them by stacking two boxes atop
another every time. This generates a new box of height at most
$2(\varepsilon+\varepsilon^{2})\mathrm{OPT}$ and width $W$. We place this wide
box atop the final packing, at height
$\nicefrac{{5}}{{4}}H+\varepsilon\mathrm{OPT}$. Clearly, this does not result
in any overlapping.
_Step 3: Reordering tall and vertical items inside the boxes._ After the
necessary condition is fulfilled, we can begin reordering the boxes in
$\mathcal{B}_{T\cup V}$. We do this by applying the either Lemma 6, Lemma 7 or
Lemma 9, depending on which of those is applicable to the box we are currently
reordering. To accurately estimate the number of generated sub-boxes we have
to assume that each box in $\mathcal{B}_{T\cup V}$ is one that generates the
largest number of sub-boxes. In our case, these are boxes with height greater
than $\nicefrac{{3}}{{4}}H$, i.e. boxes solved with Lemma 9. In every such box
$B$, we draw a vertical line at the left border of each contained sub-box. If
a sub-box for vertical items is intersected by such a line we split the sub-
box there. Each of these lines intersects at most three boxes for vertical
items, because there can be at most four boxes atop another at any point
inside $B$. Therefore, we introduce at most three new boxes per vertical line.
Since there are at most $\mathcal{O}(1/(\delta^{2}\varepsilon^{5}))$ sub-boxes
for tall and vertical items, we generate at most
$\mathcal{O}(1/(\delta^{2}\varepsilon^{5}))$ vertical lines as well. Since
each of these lines splits a constant number of boxes, the number of boxes for
vertical items after splitting is still bounded by
$\mathcal{O}(1/(\delta^{2}\varepsilon^{5}))$.
The area between two consecutive lines defines a strip where the height of all
intersected boxes does not change. Consequently, we have at most
$\mathcal{O}(1/(\delta^{2}\varepsilon^{5}))$ of these strips in total. We
define $N_{S}$ as this number of strips.
_Step 4: Placing the extra boxes for vertical items._ By Lemma 10, we need at
most $\mathcal{O}(|H_{\mathcal{V}}|+|\mathcal{B}_{P}|)$ additional boxes with
height $\nicefrac{{1}}{{4}}H$ and width $\mu W$ to place the vertical items
continuously inside the boxes, where $\mathcal{B}_{P}$ are the boxes for
vertical items created to this point. We call this set of additional boxes
$\mathcal{B}_{\mu W}$. We can bound the relevant variables as follows: There
are at most $|\mathcal{B}_{P}|\in\mathcal{O}(1/(\delta^{2}\varepsilon^{5}))$
boxes for vertical items and at most $|H_{\mathcal{V}}|\leq
1/\delta\varepsilon$ different heights of items. Therefore, we need at most
$N_{F}\in\mathcal{O}(1/(\delta^{2}\varepsilon^{5}))$ extra boxes
$\mathcal{B}_{\mu W}$.
We have to place these additional boxes inside the packing area
$W\times\nicefrac{{5}}{{4}}H$. We show that this is possible by considering
the three possibilities we outlined above. Recall the vertical lines at the
borders of boxes in $\mathcal{B}_{T\cup V}$. These $N_{L}$ many lines generate
at most $N_{L}+1$ strips. Let $W_{T}$ be the total width of the strips
containing items from $T_{\nicefrac{{1}}{{2}}H}$, $W_{H}$ the total width of
strips containing boxes of height greater than $\nicefrac{{3}}{{4}}H$ and
$W_{R}$ be the total width of the remaining strips. In total, we must have
$W_{T}+W_{H}+W_{R}=W$. Let $|\mathcal{B}_{T\cup V}|=N_{B}$. We can assume
$N_{B}\leq c_{B}/(\delta^{2}\varepsilon),N_{S}\leq
c_{S}/(\delta^{2}\varepsilon^{5}),N_{F}\leq c_{F}/(\delta^{2}\varepsilon^{5})$
and $N_{L}\leq c_{L}/(\delta^{2}\varepsilon)$ for some constants
$c_{B},c_{S},c_{F},c_{L}\in\mathbb{N}$. At this point, it is necessary to
define the function $f$ from Lemma 2 to find the values $\delta$ and $\mu$
more precisely. We specify $f(\varepsilon)$ by choosing
$k\leq(4(c_{B}+c_{F}+c_{L})c_{S}).$ Therefore,
$\mu\leq\delta^{2}\varepsilon^{11}/(4(c_{B}+c_{F}+c_{L})c_{S})$ holds.
Consider the strips that make up the value $W_{R}$, i.e. strips without boxes
of height greater than $\nicefrac{{3}}{{4}}H$ or items in
$T_{\nicefrac{{1}}{{2}}H}$. These strips can contain boxes with height larger
than $\nicefrac{{1}}{{2}}H$. Therefore, we have a free area with total width
of at least $\varepsilon^{2}W_{R}$ in these strips.

######  Claim 13.

If $W_{R}\geq\varepsilon^{4}W$, we can place the $N_{F}$ boxes
$\mathcal{B}_{\mu W}$ into the free areas in strips that comprise $W_{R}$.

######  Proof 3.8.

The considered strips might contain boxes with height larger than
$\nicefrac{{1}}{{2}}H$ but less than $\nicefrac{{3}}{{4}}H$. Otherwise, they
would have been counted in $W_{H}$. Therefore, the free area in these strips
will be partially used by extra boxes for pseudo items from these boxes.
Nevertheless, we know from Lemma 7 that these strips contain free area of
width at least $\varepsilon^{2}W_{R}$ that we can use to place the boxes
$\mathcal{B}_{\mu W}$. In each of these at most $N_{L}+1$ strips the free area
is contiguous. However, we have to calculate a small error that might occur:
Each of the boxes in $\mathcal{B}_{\mu W}$ has a width of $\mu W$ and
therefore, there is a residual width of up to $\mu W$ where we cannot place a
box from $\mathcal{B}_{\mu W}$ in each strip. See Figure 17 for an intuitive
illustration of this issue.
On the other hand, we can use an area with total width of at least
$\varepsilon^{2}W_{R}-(N_{L}+1)\mu W$ to place the boxes in $\mathcal{B}_{\mu
W}$, since there are at most $N_{L}+1$ strips. Therefore, if
$\varepsilon^{2}W_{R}-(N_{L}+1)\mu W\geq N_{F}\mu W$, we can place all the
boxes. Using $\mu:=\delta^{2}\varepsilon^{11}/(4(c_{B}+c_{F}+c_{L})c_{S})$ it
holds that

$N_{F}\mu W+(N_{L}+1)\mu W=\mu
W(c_{F}/\delta^{2}\varepsilon^{5}+c_{L}/\delta^{2}\varepsilon+1)\leq\varepsilon^{11}W/\varepsilon^{5}\leq\varepsilon^{6}W.$

Therefore, if $W_{R}\geq\varepsilon^{4}W$, it holds that
$\varepsilon^{2}W_{R}-(N_{L}+1)\mu W\geq N_{F}\mu W$ and we can place all the
boxes $\mathcal{B}_{\mu W}$, proving the claim.

$C_{1}$$C_{2}$$C_{3}$

Figure 17: An illustration of the placement of the strips containing the
additional strips of vertical items generated by Lemma 10. As you can see, we
may fail to use a width of up to $\mu W$ to place these items for each area we
find to place these items in.

With this option proven to be feasible, let us now focus our attention on
another possibility to place the boxes in $\mathcal{B}_{\mu W}$, depending on
the total width of strips containing tall items overlapping the horizontal
line at $\nicefrac{{1}}{{2}}H$. Since we have already shown how to finish the
placement of the new boxes if there is ample space in $W_{R}$, we know that
this is not the case.

######  Claim 14.

If $W_{H}<\varepsilon^{6}W/(4c_{S})$ and $W_{R}<\varepsilon^{4}W$, we can
place all the boxes for vertical items inside the boxes of height at least
$\nicefrac{{3}}{{4}}H$.

######  Proof 3.9.

Due to the definition of $W_{T}$, we know that
$W_{H}=W-(W_{T}+W_{R})>(1-2\varepsilon^{4})W\geq\varepsilon W$. Additionally,
each tall item not in $T_{\nicefrac{{1}}{{2}}H}$ crossing
$\nicefrac{{1}}{{2}}H$ has a width of at most
$W_{T}\cdot\delta^{2}\varepsilon<\varepsilon^{7}\delta^{2}W/4c_{S}:=w_{max}$.
This is because there would not be enough space left inside $W_{H}$ if these
items were any wider. After reordering the inside of the boxes, there are
$N_{S}$ strips total inside the boxes. We want to determine the total height
of free area inside a strip. This area may not be contiguous, as there can be
an item in the middle of any of these strips, with free area above and below
it. However, we can address this issue trivially by slicing this item
downwards, leaving only one contiguous area of free space. In the shifting
step, we have added a total area of
$W_{H}(\nicefrac{{1}}{{4}}H+\varepsilon\mathrm{OPT})$ to all of these strips.
Let $\breve{W_{H}}$ be the total width of the strips containing free area with
total height less than $\nicefrac{{1}}{{4}}H$. Since the boxes in
$\mathcal{B}_{\mu W}$ have a height of up to $\nicefrac{{1}}{{4}}H$, we want
to use areas with at least that height to place them. Let $\hat{W_{H}}$ be the
total width of these strips. Clearly, we have
$\breve{W_{H}}+hat{W_{H}}=W_{H}$. We have to show the following to be able to
place the extra boxes as desired:
_It holds that $\hat{W_{H}}\geq\varepsilon W_{H}$._
The total free area can have a height of at most
$\nicefrac{{3}}{{4}}\varepsilon\mathrm{OPT}$ inside each strip, because there
either are boxes at the top and bottom of height at least
$\nicefrac{{1}}{{4}}H$, or one box of height at least $\nicefrac{{3}}{{4}}H$
at the bottom. Therefore, we have

$\nicefrac{{1}}{{4}}\cdot\breve{W_{H}}+(\nicefrac{{3}}{{4}}H+\varepsilon\mathrm{OPT})\cdot\hat{W_{H}}\geq
W_{H}(\nicefrac{{1}}{{4}}H+\varepsilon\mathrm{OPT})$

since the free area in $\breve{W_{H}}$ has a total height of at most
$\nicefrac{{1}}{{4}}H$, the free area in $\hat{W_{H}}$ has a height of at most
$(\nicefrac{{3}}{{4}}H+\varepsilon\mathrm{OPT})$ and the total free area is
bounded by $W_{H}(\nicefrac{{1}}{{4}}H+\varepsilon\mathrm{OPT})$.
As a consequence, we can prove that $\hat{W_{H}}$ has a sufficient minimum
size. The following holds:

$\displaystyle
W_{H}(\nicefrac{{1}}{{4}}H+\varepsilon\mathrm{OPT})\leq\nicefrac{{1}}{{4}}H\cdot\breve{W_{H}}+(\nicefrac{{3}}{{4}}H+\varepsilon\mathrm{OPT})\cdot\hat{W_{H}}$
$\displaystyle=\nicefrac{{1}}{{4}}H\cdot
W_{H}+(\nicefrac{{1}}{{2}}H+\varepsilon\mathrm{OPT})\hat{W_{H}}$
$\displaystyle=\nicefrac{{1}}{{4}}H\cdot
W_{H}+((1+2\varepsilon)\mathrm{OPT}/2+\varepsilon\mathrm{OPT})\cdot\hat{W_{H}}$
$\displaystyle=\nicefrac{{1}}{{4}}H\cdot
W_{H}+((1+4\varepsilon)\mathrm{OPT}/2)\cdot\hat{W_{H}}.$

This allows us to deduce that

$\varepsilon W_{H}\leq((1+4\varepsilon)/2)\cdot\hat{W_{H}}.$

Therefore,

$\displaystyle\hat{W_{H}}$ $\displaystyle\geq 2\varepsilon
W_{H}/(1+4\varepsilon)\geq\varepsilon W_{H},$ $\displaystyle\forall
0<\varepsilon\leq\nicefrac{{1}}{{4}},$

which proves the claim.
As a direct consequence of this claim, strips with total width of at least
$\varepsilon W_{H}$ contain free area with total height of at least
$\nicefrac{{1}}{{4}}H$. We have already alluded to the fact that, even when
the area is split by an item in the middle, we can fuse these areas together
trivially.
In each strip, there is an area with width of at most $\mu W$ that we cannot
use to place the boxes. Therefore, we can place all boxes for previously
separated vertical items if $\varepsilon W_{H}-2w_{max}N_{S}-\mu WN_{S}\geq\mu
WN_{F}$. It holds that

$\displaystyle 2w_{max}N_{S}+\mu WN_{S}+\mu WN_{F}$
$\displaystyle\leq(\varepsilon^{7}\delta^{2}W/(2c_{S}))(c_{S}/\delta^{2}\varepsilon^{5})+\mu
W(c_{S}/\delta^{2}\varepsilon^{5}+c_{F}/\delta^{2}\varepsilon^{5})$
$\displaystyle\leq\varepsilon^{2}W/2+\varepsilon^{6}W\leq\varepsilon^{2}W.$

Thus, if $W_{H}\geq\varepsilon W$, we know that $\varepsilon
W_{H}-2w_{max}N_{S}-\mu WN_{S}\geq\mu WN_{F}$ and we can place all boxes in
the designated areas for this case.

In this step, we create at most
$2N_{S}\in\mathcal{O}(1/(\varepsilon^{5}\delta^{2}))$ new boxes for tall items
and no new box for vertical items. The boxes for tall items already contain
only tall items of the same height. Therefore, we introduce at most
$\mathcal{O}(1/(\varepsilon^{5}\delta^{2}))$ boxes for vertical items
$\mathcal{B}_{V}$ such that each box $B\in\mathcal{B}_{V}$ contains only items
with height $0pt(B)$.
_The boxes for small items._ The free area inside the boxes from the partition
in Lemma 5 for horizontal, tall and vertical items is at least as large as the
total area for the small items, because the small items where contained in the
optimal packing.
_Bounding the packing height._ To bound the total height of the packing we
summarize which heights we added during the process so far. In the beginning,
we had the optimal packing of height $\mathrm{OPT}$. Through our rounding with
Lemma 3, we generated a packing of height $(1+2\varepsilon)\mathrm{OPT}$. When
we extended boxes containing tall and vertical items of height at least
$\nicefrac{{3}}{{4}}H$, we added
$\nicefrac{{1}}{{4}}H+\varepsilon\mathrm{OPT}\leq\nicefrac{{1}}{{4}}(1+2\varepsilon)\mathrm{OPT}+\varepsilon\mathrm{OPT}$
to the packing height. Earlier in this proof, to ensure that all boxes with
height greater than $\nicefrac{{1}}{{2}}H$ start and end at multiples of
$\varepsilon^{2}\mathrm{OPT}$ we shifted some vertical items. This procedure
added a further $2(\varepsilon+\varepsilon^{2})\mathrm{OPT}$ to the packing
height. Thus, in total, we have added at most
$\nicefrac{{1}}{{4}}(1+2\varepsilon)\mathrm{OPT}+2(\varepsilon+\varepsilon^{2})\mathrm{OPT}\leq(\nicefrac{{1}}{{4}}+3\varepsilon)\mathrm{OPT}$
to the packing height. This assumes sufficiently small, i.e. smaller than
$\nicefrac{{1}}{{2}}$ values for $\varepsilon$. As such, the structured
packing has a height of at most
$(\nicefrac{{5}}{{4}}+5\varepsilon)\mathrm{OPT}$.

We employ a dynamic program to iterate through all possible configurations of
these boxes until we find a feasible packing of the items into the boxes.

#### Step 6

We utilize some techniques developed in [15] to place the small and medium
items without exceeding the desired height of the packing.

######  Lemma 15.

It is possible to place the small items inside the boxes $\mathcal{B}_{V}^{S}$
and $\mathcal{B}_{H}^{S}$ and one extra box with width $W$ and height at most
$2\varepsilon\delta^{6}\mathrm{OPT}.$

######  Proof 3.10.

This is an adaptation of a similar procedure in [15], considering the slicing
of items. Recall how we started partitioning the original optimal packing into
the boxes in Lemma 5. Since this optimal packing contained the small items as
well as the items we chose as the basis of our partitioning, the total
remaining area inside those boxes must be enough to place these small items.
In Lemmas 10 and 11 we generate at most
$\mathcal{O}(1/(\varepsilon^{5}\delta^{2}))$ empty boxes which we can use to
place the small items. We have shown that the total area of those empty boxes
is at least as large as the empty space left in the original boxes
$\mathcal{B}_{H}$ and $\mathcal{B}_{T\cup V}$ in Lemma 5. As $\mathcal{B}_{L}$
only ever contain a single item, there is no empty space in these boxes.
Therefore, the total area in those empty boxes is at least as large as the
total area of small items.
Let $\mathcal{B}_{S}$ be the set of boxes for small items and
$|\mathcal{B}_{S}|=c/\delta^{2}\varepsilon^{5}$ for some constant
$c\in\mathbb{N}$. We show that we only need one small extra box to place all
the small items into $\mathcal{B}_{S}$ using the Next Fit Decreasing Height
(NFDH) algorithm[17].
First, we discard any box that is too small in either dimension, i.e. has a
height of less than $\mu\mathrm{OPT}$ or a width of $\mu W$. Clearly, the
total area of discarded boxes is at most $\mu W\mathrm{OPT}$. Consider a box
$B$ with height and width greater than $\mu\mathrm{OPT}$ and $\mu W$
respectively. The last item we want to place on each shelf during the NFDH-
Algorithm might not fit from its width. As such, we may have an empty space of
at most $\mu W$ on each shelf, as all small items have at most that width.
Furthermore, the final shelf has a distance of at most $\mu\mathrm{OPT}$ to
the top border of $B$. Again, this area might remain free if no suitable items
are left. Finally, the free area between two shelves used in the algorithm has
a size of at most $\mu\mathrm{OPT}\cdot w(B)$, again because all small items
have at most that size. As a result, the total free area inside the box $B$ is
at most $\mu W\cdot 0pt(B)+2\mu\mathrm{OPT}\cdot 0pt(B)\leq 3\mu
W\mathrm{OPT}$. We have this free area for every box $B\in\mathcal{B}_{S}$.
Therefore, the total area of items that could not be placed inside boxes is at
most $3\mu W\mathrm{OPT}\cdot c/\delta^{2}\varepsilon^{5}.$ Since we have
defined $\mu\leq\varepsilon^{11}\delta^{2}/k$ for some suitable constant $k$
through Lemma 2 it holds that $3\mu W\mathrm{OPT}\cdot
c/\delta^{2}\varepsilon^{5}\leq\varepsilon^{6}W\mathrm{OPT}$ when choosing
$k\geq c$.
These remaining items can then be placed into a box of width $W$ and height
$2\varepsilon^{6}\mathrm{OPT}$ using Steinbergs algorithm [27]. The relevant
conditions to apply this algorithm are met because each item has a height of
at most $\mu\mathrm{OPT}$.

Having placed the small items, there is only one set of items left to place
before we have successfully shown that our partition into boxes allows us to
generate a structured packing while only adding a height of
$(\nicefrac{{1}}{{4}})\mathrm{OPT}+\mathcal{O}(\varepsilon\mathrm{OPT})$ to
the top of the packing. Thus, we now show that the medium items, of which
there are few, can be placed in a structured manner.

######  Lemma 16.

[15] It is possible to place the medium items $M$ into a box of width $W$ and
height at most $2\varepsilon\mathrm{OPT}$.

######  Proof 3.11.

We know, from Lemma 2, that the total area of medium items is small. Thus, we
use a well defined algorithm to place these items at an approximately greater
loss. As we did with the small items, we use the NFDH algorithm for this
purpose [17]. Before we apply the algorithm, we sort all items by their width,
in descending manner. We know that $a(M)$ is bounded by
$\varepsilon^{13}W\mathrm{OPT}$ and the widest item in $M$ has a width of at
most $\varepsilon\mathrm{OPT}$. Therefore, we can place these items in a box
of width $W$ and height of at most
$2\varepsilon^{13}\mathrm{OPT}+\varepsilon\mathrm{OPT}\leq
2\varepsilon\mathrm{OPT}$.

#### Step 7

The algorithm iterates over the previous steps until the minimal value for
$H^{\prime}$ has been found and returns the associated packing. Because we
have shown that any optimal packing of height $\mathrm{OPT}$ can be
transformed into a structured packing of height
$(\nicefrac{{5}}{{4}}+\varepsilon)\mathrm{OPT}$, we know that
$H^{\prime}\leq\mathrm{OPT}$ must hold. Therefore, our algorithm generates a
solution with height at most the desired approximation ratio.

#### Running time:

Scaling the instance can be done in $\mathcal{O}(n\log(n))$. The binary search
in step $2$ runs logarithmically in its step-length. Due to our rounding, this
length is $n/\varepsilon$. Therefore, the search can be computed in
$\mathcal{O}(\log(n/\varepsilon))$. For every value of the search, we have to
guess the starting points for horizontal items. As there are
$\mathcal{O}_{\varepsilon}(1)$ of these boxes, we can guess these in
$W^{\mathcal{O}_{\varepsilon}(1)}$ time. Then, we guess all possible
configurations of boxes inside the packing. Again, there are
$\mathcal{O}_{\varepsilon}(1)$ many of those, yielding a running time of
$W^{\mathcal{O}_{\varepsilon}(1)}$ for this step. As a result, the running
time can be expressed as
$\mathcal{O}(n\log(n))+\mathcal{O}(\log(n/\varepsilon))\cdot
W^{\mathcal{O}_{\varepsilon}(1)}=\mathcal{O}(n\log(n))\cdot
W^{\mathcal{O}_{\varepsilon}(1)}.$ This completes the proof of Theorem 5.

##  4 Conclusion

We showed that the Demand Strip Packing problem remains hard to solve with an
approximation ratio lower than $(\nicefrac{{5}}{{4}})\cdot\mathrm{OPT}$, even
in pseudo-polynomial time. In the process of this proof, we developed a
transformation algorithm showing that we can treat DSP and PTS as somewhat
dual problems of one another. We provided a framework using known results to
solve either of these problems optimally when admitting some resource
augmentation. These results are valuable in applications where penalty costs
for exceeding makespan or power demand are large.

Finally, we have developed an approximation algorithm for DSP that runs in
pseudo-polynomial time. The adaptations made bridge the known integrality gap
between SP and DSP. Furthermore, its approximation ratio of
$(\nicefrac{{5}}{{4}}+\varepsilon)\cdot\mathrm{OPT}$ almost matches the proven
hardness except for a negligibly small $\varepsilon$. As a contrast, in
polynomial time, the gap between proven hardness $(\nicefrac{{3}}{{2}})$ [31]
and best-known approximation $(\nicefrac{{5}}{{3}}+\varepsilon)$ [3, 6]
remains quite large.

Similar results for the SP algorithm suggest that the presented algorithm can
be adapted to admit 90° item rotations or moldable jobs. Both of these
settings are interesting in the context of smart grids. Rotations can model
different modes of power consumption, i.e. fast versus slow charging. Moldable
jobs can model the parallel operation of multiple machines for the same task.
Each variation on the job/item represents a set number of machines assigned to
that task.

Further open questions extend to the relation of DSP to other packing
problems. A family of instances exists where the height of optimal solutions
for SP and DSP differs by 5/4 [2]. Furthermore, due to Steinbergs’ algorithm,
this difference is bounded by 2. Closing this gap might imply better bounds on
optimal solutions for either problem.

On the other hand, the discovered link between DSP and PTS may suggest similar
links between DSP and other resource allocation problems. Amongst these, the
well-known Storage Allocation Problem (SAP) [20] and Unsplittable Flow on a
Path (UFP) [9] problems are promising candidates. So far, a PTAS is known only
for the latter [8]. Techniques used in the presented algorithm may be helpful
in adapting existing algorithms for SAP to UFP, or vice versa. Furthermore,
similar resource augmentation arguments as we made for PTS and DSP may be made
for either problem should a link between DSP and UFP or SAP exist. Finally,
techniques used in the presented approximation scheme may be useful when
developing an approximation scheme for SAP.

## References

  * [1] Brenda S. Baker, Edward G. Coffman Jr., and Ronald L. Rivest.  Orthogonal packings in two dimensions.  SIAM J. Comput., 9(4):846–855, 1980.
  * [2] Iwo Bladek, Maciej Drozdowski, Frédéric Guinand, and Xavier Schepler.  On contiguous and non-contiguous parallel task scheduling.  J. Sched., 18(5):487–495, 2015.
  * [3] Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas.  Peak demand minimization via sliced strip packing.  In APPROX-RANDOM, volume 207 of LIPIcs, pages 21:1–21:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [4] G. Dileep.  A survey on smart grid technologies and applications.  Renewable Energy, 146:2589–2625, 2020.
  * [5] Jianzhong Du and Joseph Y.-T. Leung.  Complexity of scheduling parallel task systems.  SIAM J. Discret. Math., 2(4):473–487, 1989.
  * [6] Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi.  Approximation algorithms for demand strip packing.  CoRR, abs/2105.08577, 2021.
  * [7] Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan.  Improved pseudo-polynomial-time approximation for strip packing.  In FSTTCS, volume 65 of LIPIcs, pages 9:1–9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [8] Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese.  A PTAS for unsplittable flow on a path.  In STOC, pages 289–302. ACM, 2022.
  * [9] Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese.  Unsplittable flow on a path: The game!  In SODA, pages 906–926. SIAM, 2022.
  * [10] Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee.  A (5/3 + $\epsilon$)-approximation for strip packing.  Comput. Geom., 47(2):248–267, 2014.
  * [11] Rolf Harren and Rob van Stee.  Improved absolute approximation ratios for two-dimensional packing problems.  In APPROX-RANDOM, volume 5687 of Lecture Notes in Computer Science, pages 177–189. Springer, 2009.
  * [12] Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje.  Complexity and inapproximability results for parallel task scheduling and strip packing.  In CSR, volume 10846 of Lecture Notes in Computer Science, pages 169–180. Springer, 2018.
  * [13] Dorit S. Hochbaum and David B. Shmoys.  Using dual approximation algorithms for scheduling problems theoretical and practical results.  J. ACM, 34(1):144–162, 1987.
  * [14] Klaus Jansen and Malin Rau.  Improved approximation for two dimensional strip packing with polynomial bounded width.  In WALCOM, volume 10167 of Lecture Notes in Computer Science, pages 409–420. Springer, 2017.
  * [15] Klaus Jansen and Malin Rau.  Closing the gap for pseudo-polynomial strip packing.  In ESA, volume 144 of LIPIcs, pages 62:1–62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [16] Klaus Jansen and Ralf Thöle.  Approximation algorithms for scheduling parallel jobs.  SIAM J. Comput., 39(8):3571–3615, 2010.
  * [17] Edward G. Coffman Jr., M. R. Garey, David S. Johnson, and Robert Endre Tarjan.  Performance bounds for level-oriented two-dimensional packing algorithms.  SIAM J. Comput., 9(4):808–826, 1980.
  * [18] Landis D. Kannberg, David P. Chassin, John G. DeSteese, Steve G. Hauser, Michael C. Kintner-Meyer, Robert G. Pratt, Lawrence A. Schienbein, and W. Michael Warwick.  Gridwisetm: The benefits of a transformed energy system.  Technical report, Pacific Northwest National Laboratory, 2003.
  * [19] Mohammad M. Karbasioun, Gennady Shaikhet, Ioannis Lambadaris, and Evangelos Kranakis.  Asymptotically optimal scheduling of random malleable demands in smart grid.  Discret. Math. Algorithms Appl., 10(2):1850025:1–1850025:25, 2018\.
  * [20] Tobias Mömke and Andreas Wiese.  Breaking the barrier of 2 for the storage allocation problem.  In ICALP, volume 168 of LIPIcs, pages 86:1–86:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [21] Giorgi Nadiradze and Andreas Wiese.  On approximating strip packing with a better ratio than 3/2.  In SODA, pages 1491–1510. SIAM, 2016.
  * [22] Anshu Ranjan, Pramod Khargonekar, and Sartaj Sahni.  Offline preemptive scheduling of power demands to minimize peak power in smart grids.  In 2014 IEEE Symposium on Computers and Communications (ISCC), pages 1–6. IEEE, 2014.
  * [23] Anshu Ranjan, Pramod Khargonekar, and Sartaj Sahni.  Offline first fit scheduling in smart grids.  In 2015 IEEE Symposium on Computers and Communication (ISCC), pages 758–763. IEEE, 2015.
  * [24] Ingo Schiermeyer.  Reverse-fit: A 2-optimal algorithm for packing rectangles.  In ESA, volume 855 of Lecture Notes in Computer Science, pages 290–299. Springer, 1994.
  * [25] Pierluigi Siano.  Demand response and smart grids—a survey.  Renewable and sustainable energy reviews, 30:461–478, 2014.
  * [26] Daniel Dominic Sleator.  A 2.5 times optimal algorithm for packing in two dimensions.  Inf. Process. Lett., 10(1):37–40, 1980.
  * [27] A. Steinberg.  A strip-packing algorithm with absolute performance bound 2.  SIAM J. Comput., 26(2):401–409, 1997.
  * [28] Shaojie Tang, Qiuyuan Huang, Xiang-Yang Li, and Dapeng Wu.  Smoothing the energy consumption: Peak demand reduction in smart grid.  In 32nd IEEE International Conference on Computer Communications (INFOCOM), pages 1133–1141. IEEE, 2013.  doi:10.1109/INFCOM.2013.6566904.
  * [29] Shaojie Tang, Qiuyuan Huang, Xiang-Yang Li, and Dapeng Wu.  Smoothing the energy consumption: Peak demand reduction in smart grid.  In 2013 Proceedings IEEE INFOCOM, 2013.
  * [30] Jacopo Torriti.  Peak Energy Demand and Demand Side Response.  Routledge, 2016.
  * [31] Sean Yaw, Brendan Mumey, Erin McDonald, and Jennifer Lemke.  Peak demand scheduling in the smart grid.  In 2014 IEEE international conference on smart grid communications (SmartGridComm), pages 770–775. IEEE, 2014.