University of Wrocław University of Wrocław University of Wrocław Theory of
computation Online algorithms Supported by Polish National Science Centre

grant 2022/45/B/ST6/00559.
_For the purpose of open access, the authors have applied CC-BY public
copyright licence to any Author Accepted Manuscript (AAM) version arising from
this submission._

# An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem

Mateusz Basiak  Marcin Bienkowski  Agnieszka Tatarczuk

###### Abstract

We study the online variant of the Min-Sum Set Cover (Mssc) problem, a
generalization of the well-known list update problem. In the Mssc problem, an
algorithm has to maintain the time-varying permutation of the list of $n$
elements, and serve a sequence of requests $R_{1},R_{2},\dots,R_{t},\dots$.
Each $R_{t}$ is a subset of elements of cardinality at most $r$. For a
requested set $R_{t}$, an online algorithm has to pay the cost equal to the
position of the first element from $R_{t}$ on its list. Then, it may
arbitrarily permute its list, paying the number of swapped adjacent element
pairs.

We present the first _constructive_ deterministic algorithm for this problem,
whose competitive ratio does not depend on $n$. Our algorithm is
$O(r^{2})$-competitive, which beats both the _existential_ upper bound of
$O(r^{4})$ by Bienkowski and Mucha [AAAI ’23] and the previous constructive
bound of $O(r^{3/2}\cdot\sqrt{n})$ by Fotakis et al. [ICALP ’20]. Furthermore,
we show that our algorithm attains an asymptotically optimal competitive ratio
of $O(r)$ when compared to the best fixed permutation of elements.

###### keywords:

min-sum set cover, list update, derandomization, online algorithms,
competitive analysis

##  1 Introduction

In the online Min-Sum Set Cover (Mssc) problem [12, 13], an algorithm has to
maintain an ordered list of elements. During runtime, an online algorithm is
given a sequence of requests $R_{1},R_{2},\dots,R_{t},\dots$, each being a
subset of elements. When a request $R_{t}$ appears, an algorithm first pays
the cost equal to the position of the first element of $R_{t}$ in its list.
Next, it may arbitrarily reorder the list, paying the number of swapped
adjacent elements.

The online Mssc finds applications in e-commerce, for maintaining an ordered
(ranked) list of all shop items (elements) to be presented to new shop
customers [9]. This so-called cold-start list can be updated to reflect the
preferences of already known users (where $R_{t}$ corresponds to the set of
items that are interesting for user $t$). Each user should be able to find at
least one interesting item close to the list beginning, as otherwise, they
must scroll down, which could degrade their overall experience. Similar
phenomena occur also in ordering results from a web search for a given keyword
[10, 1], or ordering news and advertisements.

The problem is also theoretically appealing as the natural generalization of
the well-known list update problem [16], where all $R_{t}$ are singletons (see
[14] and references therein).

###  1.1 Model and notation

For any integer $\ell$, let $[\ell]=\\{1,\dots,\ell\\}$. We use $\mathcal{U}$
to denote the universe of $n$ elements. By permutation $\pi$ of $\mathcal{U}$,
we understand a mapping $\mathcal{U}\to[n]$ (from items to their list
positions). Thus, for an element $z\in\mathcal{U}$, $\pi(z)$ is its position
on the list.

An input $\mathcal{I}$ to the online Mssc problem consists of an initial
permutation $\pi_{0}$ of $\mathcal{U}$ and a sequence of $m$ sets
$R_{1},R_{2},\dots,R_{m}$. In step $t$, an online algorithm Alg is presented a
request $R_{t}$ and is charged the _access cost_ $\min_{z\in
R_{t}}\pi_{t-1}(z)$. Then, Alg chooses a new permutation $\pi_{t}$ (possibly
$\pi_{t}=\pi_{t-1}$) paying _reordering cost_ $d(\pi_{t-1},\pi_{t})$, equal to
the minimum number of swaps of adjacent elements necessary to change
permutation $\pi_{t-1}$ into $\pi_{t}$.111The value $d(\pi_{t-1},\pi_{t})$ is
also equal to the number of inversions between $\pi_{t-1}$ and $\pi_{t}$,
i.e., number of unordered pairs $(x,y)$ such that $\pi_{t-1}(x)<\pi_{t-1}(y)$
and $\pi_{t}(x)>\pi_{t}(y)$.

We emphasize that the choice of $\pi_{t}$ made by Alg has to be performed
without the knowledge of future sets $R_{t+1},R_{t+2},\dots$ and also without
the knowledge of the sequence length $m$. We use $r$ to denote the maximum
cardinality of requested sets $R_{t}$.

###  1.2 Benchmarks

In the following, for an input $\mathcal{I}$ and an algorithm $A$, we use
$A(\mathcal{I})$ to denote the total cost of $A$ on $\mathcal{I}$. To measure
the effectiveness of online algorithms, we use the standard notion of
competitive ratio, but we generalize it slightly, for more streamlined
definitions of particular scenarios.

We say that an online algorithm Alg is $c$-competitive _against class
$\mathcal{C}$ of offline algorithms_ if there exists a constant $\xi$, such
that for any input $\mathcal{I}$ and any offline algorithm
$\textnormal{{Off}}\in\mathcal{C}$, it holds that
$\textnormal{{Alg}}(\mathcal{I})\leq
c\cdot\textnormal{{Off}}(\mathcal{I})+\xi$. If $\xi=0$, then Alg is called
_strictly_ competitive. The competitive ratio of Alg against class
$\mathcal{C}$ is the infimum of values of $c$, for which Alg is
$c$-competitive against this class. For randomized algorithms, we replace the
cost $\textnormal{{Alg}}(\mathcal{I})$ with its expected value
$\mathbf{E}[\textnormal{{Alg}}(\mathcal{I})]$. We consider three scenarios.

#### Dynamic scenario.

In the dynamic scenario, the considered class $\mathcal{C}$ contains all
possible offline algorithms, in particular those that adapt their permutation
dynamically during runtime. This setting is equivalent to the traditional
competitive ratio [8], where an online algorithm is compared to the optimal
offline solution Opt. This scenario is the main focus of this paper.

#### Static scenario.

Previous papers focused also on a simpler _static scenario_ , where the
considered class of algorithms Fixed contains all possible $n!$ fixed
strategies: an algorithm from class Fixed starts with its list ordered
according to a fixed permutation and never changes it [12]. (In this scenario,
the starting permutation of an online algorithm and an offline solution are
different.) Note that such an offline algorithm incurs no reordering cost, and
pays access costs only. It is worth mentioning that there exist inputs
$\mathcal{I}$, for which
$\min_{A\in\textsc{Fixed}}A(\mathcal{I})=\Omega(n)\cdot\textnormal{{Opt}}(\mathcal{I})$
[12].

#### Learning scenario.

The static scenario can be simplified further, by assuming that reordering
incurs no cost on Alg. We call such a setting _learning scenario_. Clearly,
the competitive ratios achievable in the learning scenario are not larger than
those for the static scenario, which are in turn not larger than those in the
dynamic scenario.

###  1.3 Previous results

Below, we discuss known results for the Mssc problem in the three scenarios
described above (dynamic, static, and learning). Furthermore, we make a
distinction between ratios achievable for polynomial-time algorithms and
algorithms whose runtime per request is not restricted. The lower and upper
bounds described below are also summarized in Table 1.

#### Lower bounds.

Feige et al. [11] studied the _offline_ variant of Mssc (where all $R_{t}$’s
are given upfront and an algorithm has to compute a fixed permutation
minimizing the access cost). They show that unless $\textsf{P}=\textsf{NP}$,
no offline algorithm can achieve an approximation ratio better than $4$. This
result implies a lower bound of $4$ on the competitive ratio of any
polynomial-time online algorithm (assuming $\textsf{P}\neq\textsf{NP}$) as
such a solution can be used to solve the offline variant as well. We note that
$4$-approximation algorithms for the offline variant are known as well [11,
4].

The online version of Mssc was first studied by Fotakis et al. [12]. They show
that no deterministic algorithm can achieve a ratio better than $\Omega(r)$
even in the learning scenario. This yields the same lower bound for the
remaining scenarios as well.

| randomized | deterministic
---|---|---
LB | UB | LB | UB
learning | unrestr. | $1$ | $1+\varepsilon$ |  $\Omega(r)$ [12] | $O(r)$
poly-time |  $4$ [11] |  $11.713$ [13] | $\Omega(r)$ |  $O(r)$ [13]
static | unrestr. | $1$ |  $1+\varepsilon$ [7] | $\Omega(r)$ |  $O(r)$ [12]
poly-time | $4$ | $O(r^{2})$ | $\Omega(r)$ |  $\exp(O(\sqrt{\log n\cdot\log r}))$ [12]
$\bm{O(r)}$ (Theorem 4.7) |  $\bm{O(r)}$ (Theorem 4.7)
dynamic | unrestr. | $1$ | $O(r^{2})$ | $\Omega(r)$ |  $O(r^{4})$ [6]
$\bm{O(r^{2})}$ (Theorem 5.4)
poly-time | $4$ | $O(r^{2})$ [6] | $\Omega(r)$ |  $O(r^{3/2}\cdot\sqrt{n})$ [12]
$\bm{O(r^{2})}$ (Theorem 5.4)
Table 1: Known lower and upper bounds for the online Mssc problem for three
scenarios (dynamic, static and learning), for polynomial-time and
computationally unrestricted algorithms. Unreferenced results are trivial
consequences of other results. The ratios proved in this paper are in bold.

#### Asymptotically tight upper bounds.

For the static scenario, the randomized $(1+\varepsilon)$-competitive solution
(for any $\varepsilon>0$) follows by combining multiplicative weight updates
[15, 2] with the techniques of Blum and Burch [7] designed for the metrical
task systems. This approach has been successfully derandomized by Fotakis et
al. [12], who gave a deterministic solution with an asymptotically optimal
ratio of $O(r)$. These algorithms clearly also work in the learning scenario.
However, in both scenarios, they require exponential time as they keep track
of access costs for all possible $n!$ permutations.

Fotakis et al. [13] showed that in the learning scenario, one can maintain a
sparse representation of all permutations and achieve asymptotically optimal
results that work in polynomial time: a randomized $O(1)$-competitive
algorithm and a deterministic $O(r)$-competitive one.

#### Non-tight upper bounds.

Much of the effort in the previous papers was devoted to creating algorithms
for the dynamic scenario with low competitive ratios. For $r=1$, a simple
Move-To-Front policy that moves the requested element to the first position is
$O(1)$-competitive Perhaps surprisingly, however, the competitive ratios of
many of its natural generalizations were shown to be not better than
$\Omega(n)$ [12].

Fotakis et al. [12] gave an online deterministic
$O(r^{3/2}\cdot\sqrt{n})$-competitive algorithm Move-All-Equally (Mae) and
showed that its analysis is almost tight. They provided a better bound for the
performance of Mae in the static scenario: in such a setting its competitive
ratio is $\exp(O(\sqrt{\log n\cdot\log r}))$ [12].

For randomized solutions, this result was improved by Bienkowski and Mucha
[6], who gave an $O(r^{2})$-competitive _randomized_ algorithm Lma (for the
dynamic scenario). Their analysis holds also against so-called adaptive-online
adversaries, and therefore, by the reduction of [5], it implies the
_existence_ of a deterministic $O(r^{4})$-competitive algorithm. While using
the techniques of Ben-David et al. [5], the construction of such an algorithm
is possible, it was not done explicitly, and furthermore, a straightforward
application of these techniques would lead to a huge running time.

###  1.4 Our contribution

In section 2, we present the first constructive deterministic algorithm whose
competitive ratio in the dynamic scenario is a function of $r$ only (and does
not depend on $n$). Our algorithm, dubbed Deterministic-And-Lazy-Move-To-Front
(Dlm), runs in polynomial time, and we analyze its performance both in static
and dynamic scenarios.

In the static scenario, studied in section 4, Dlm attains the optimal
competitive ratio of $O(r)$, improving over the $\exp(O(\sqrt{\log n\cdot\log
r}))$-competitive solution by Fotakis et al. [12] and matching $O(r)$ bound
achieved by the exponential-time algorithm of [12].

In the dynamic scenario, studied in section 5, we show that Dlm is
$O(r^{2})$-competitive. As $r\leq n$, this bound is always better than the
existing non-constructive upper bound of $O(r^{4})$ [6] and the polynomial-
time upper bound of $O(r^{3/2}\cdot\sqrt{n})$ [12]. Our analysis is
asymptotically tight: in Appendix A, we show that the ratio of $O(r^{2})$ is
best possible for the whole class of approaches that includes Dlm.

Finally, as the learning scenario is not harder than the static one, Dlm is
$O(r)$-competitive also there. While an upper bound of $O(r)$ was already
known for the learning scenario [13], our algorithm uses a vastly different,
combinatorial approach and is also much faster.

Our deterministic solution is inspired by the ideas for the randomized
algorithm Lma of [6] and can be seen as its derandomization, albeit with
several crucial differences.

  * •

We simplify their approach as we solve the Mssc problem directly, while they
introduced an intermediate exponential caching problem.

  * •

We update item budgets differently, which allows us to obtain an optimal ratio
for the static scenario (Lma is not better in the static scenario than in the
dynamic one).

  * •

Most importantly, [6] uses randomization to argue that Lma makes bad choices
with a small probability. In this context, bad choices mean moving elements
that Opt has near the list front towards the list tail in the solution of Lma.
In the deterministic approach, we obviously cannot prove the same claim, but
we show that it holds on the average. Combining this claim with the amortized
analysis, by “encoding” it in the additional potential function $\Psi$, is the
main technical contribution of our paper.

##  2 Our algorithm DLM

Dlm maintains a budget $b(z)$ for any element $z\in\mathcal{U}$. At the
beginning of an input sequence, all budgets are set to zero.

In the algorithm description, we skip step-related subscripts when it does not
lead to ambiguity, and we simply use $\pi(z)$ to denote the _current_ position
of element $z$ in the permutation of Dlm.

1 for  _$i=\pi(z),\dots,3,2$_ do

2 swap elements on positions $i$ and $i-1$

3

$b(z)\leftarrow 0$

Routine 1 fetch(z), where $z$ is any element

At certain times, Dlm moves an element $z$ to the list front. It does so using
a straightforward procedure fetch(z) (cf. Routine 1). It uses $\pi(z)-1$ swaps
that move $z$ to the first position, and increment the positions of all
elements that preceded $z$. Next, it resets the budget of $z$ to zero.

Assume now that Dlm needs to serve a request
$R=\\{x,y_{1},y_{2},\dots,y_{s-1}\\}$ (where $s\leq r$ and $\pi(x)<\pi(y_{i})$
for all $y_{i}$). Let $\ell=\pi(x)$. Dlm first executes routine
${\textsc{fetch}}(x)$. Afterward, it performs a lazy counterpart of moving
elements $y_{i}$ towards the front: it increases their budgets by $\ell/s$.
Once a budget of any element reaches or exceeds its current position, Dlm
fetches it to the list front. The pseudocode of Dlm on request $R$ is given in
Algorithm 2.

3 $\ell\leftarrow\pi(x)$

4 execute ${\textsc{fetch}}(x)$

5 for  _$i=1,2,\dots,s-1$_ do

6 $b(y_{i})\leftarrow b(y_{i})+\ell/s$

7while  _exists $z$ such that $b(z)\geq\pi(z)$_ do

8 execute ${\textsc{fetch}}(z)$

Input: request $R=\\{x,y_{1},y_{2},\dots,y_{s-1}\\}$, where $s\leq r$ and
$\pi(x)\leq\pi(y_{i})$ for $i\in[s-1]$, current permutation $\pi$ of elements

Algorithm 2 A single step of Deterministic-Lazy-Move-All-To-Front (Dlm)

Input: request $R=\\{x,y_{1},y_{2},\dots,y_{s-1}\\}$, where $s\leq r$ and
$\pi(x)\leq\pi(y_{i})$ for $i\in[s-1]$, current permutation $\pi$ of elements

##  3 Basic properties and analysis framework

We start with some observations about elements’ budgets; in particular, we
show that Dlm is well defined, i.e., it terminates.

######  Lemma 3.1.

Dlm terminates after every request.

######  Proof 3.2.

Let $C=\\{z\in\mathcal{U}\;\mid\;b(z)\geq\pi(z)\\}$. It suffices to show that
the cardinality of $C$ decreases at each iteration of the while loop in
algorithm 2 of Algorithm 2. To this end, observe that in each iteration, we
execute operation ${\textsc{fetch}}(z)$ for some $z\in C$. In effect, the
budget of $z$ is set to $0$, and thus $z$ is removed from $C$. The positions
of elements that preceded $z$ are incremented without changing their budget:
they may only be removed from $C$ but not added to it.

Once Dlm finishes list reordering in a given step, $b(z)<\pi(z)$ for any
element $z\in\mathcal{U}$. Moreover, $b(z)<(3/2)\cdot\pi(z)$ also during list
reordering.

######  Proof 3.3.

Once the list reordering terminates, by 3.1 and the while loop in Lines 2–2 of
Algorithm 2, $b(z)<\pi(z)$ for any element $z$.

Within a step, the budgets are increased only for elements $y_{i}\in R$, i.e.,
only when $s\geq 2$. The budget of such an element $y_{i}$ is increased from
at most $\pi(y_{i})$ by $\pi(x)/s\leq\pi(x)/2<\pi(y_{i})/2$, i.e., its
resulting budget is smaller than $(3/2)\cdot\pi(y_{i})$.

###  3.1 Amortized analysis

In our analysis, we compare the cost in a single step of Dlm to the
corresponding cost of an offline solution Off. For a more streamlined analysis
that will yield the result both for the static and dynamic scenarios, we split
each step into two stages. In the first stage, both Dlm and Off pay their
access costs, and then Dlm reorders its list according to its definition. In
the second stage, Off reorders its list. Note that the second stage exists
only in the dynamic scenario.

We use $\pi$ and $\pi^{*}$ to denote the current permutation of Dlm and Off,
respectively. We introduce two potential functions $\Phi$ and $\Psi$, whose
values depend only on $\pi$ and $\pi^{*}$.

In section 4, we show that in the first stage of any step, it holds that

$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq
O(r)\cdot\Delta\textnormal{{Off}}.$ (1)

where $\Delta\textnormal{{Dlm}}$, $\Delta\textnormal{{Off}}$, $\Delta\Phi$,
and $\Delta\Psi$ denote increases of the costs of Dlm and Off and the
increases of values of $\Phi$ and $\Psi$, respectively. Relation (1) summed
over all $m$ steps of the input sequence yields the competitive ratio of
$O(r)$ of Dlm in the static scenario (where only the first stage is present).

In section 5, we analyze the performance of Dlm in the dynamic scenario. We
say that an offline algorithm Off is _MTF-based_ if, for any request, it moves
one of the requested elements to the first position of the list and does not
touch the remaining elements. We define a class Mtfb of all MTF-based offline
algorithms. We show that in the second stage of any step, it holds that

$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq
O(r^{2})\cdot\Delta\textnormal{{Off}}.$ (2)

for any $\textnormal{{Off}}\in\textnormal{{Mtfb}}$. Now, summing relations (1)
and (2) over all steps in the input yields that Dlm is $O(r^{2})$-competitive
against the class Mtfb. We conclude by arguing that there exists an MTF-based
algorithm $\textnormal{{Off}}^{*}$ which is a $4$-approximation of the optimal
solution Opt.

###  3.2 Potential function

To define potential functions, we first split $\pi(z)$ into two summands,
$\pi(z)=2^{p(z)}+q(z)$, such that $p(z)$ is a non-negative integer, and
$q(z)\in\\{0,\dots,2^{p(z)}-1\\}$. We split $\pi^{*}(z)$ analogously as
$\pi^{*}(z)=2^{p^{*}(z)}+q^{*}(z)$.

We use the following parameters: $\alpha=2$, $\gamma=5r$, $\beta=7.5r+5$, and
$\kappa=\lceil\log(6\beta)\rceil$. Our analysis does not depend on the
specific values of these parameters, but we require that they satisfy the
following relations.

######  Fact 1.

Parameters $\alpha$, $\beta$ and $\gamma$ satisfy the following relations:
$\alpha\geq 2$, $\gamma\geq(3+\alpha)\cdot r$, $\beta\geq
3+\alpha+(3/2)\cdot\gamma$. Furthermore, $\kappa$ is an integer satisfying
$2^{\kappa}\geq 6\beta$.

For any element $z$, we define its potentials

$\Phi_{z}=\begin{cases}\alpha\cdot b(z)&\text{if $p(z)\leq
p^{*}(z)+\kappa$,}\\\ \beta\cdot\pi(z)-\gamma\cdot b(z)&\text{if $p(z)\geq
p^{*}(z)+\kappa+1$.}\end{cases}$ (3) $\Psi_{z}=\begin{cases}0&\text{if
$p(z)\leq p^{*}(z)+\kappa-1$,}\\\ 2\beta\cdot q(z)&\text{if $p(z)\geq
p^{*}(z)+\kappa$.}\end{cases}$ (4)

We define the total potentials as $\Phi=\sum_{z\in\mathcal{U}}\Phi_{z}$ and
$\Psi=\sum_{z\in\mathcal{U}}\Psi_{z}$.

######  Lemma 3.4.

At any time and for any element $z$, $\Phi_{z}\geq 0$ and $\Psi_{z}\geq 0$.

######  Proof 3.5.

The relation $\Psi_{z}\geq 0$ follows trivially from (4). By Fact 1,
$\beta\geq(3/2)\cdot\gamma$. This, together with section 3, implies that
$\Phi_{z}\geq 0$.

###  3.3 Incrementing elements positions

We first argue that increments of elements’ positions induce small changes in
their potentials. Such increments occur for instance when Dlm fetches an
element $z$ to the list front: all elements that preceded $z$ are shifted by
one position towards the list tail. We show this property for the elements on
the list of Dlm first and then for the list of Off.

We say that an element $w$ is _safe_ if $p(w)\leq p^{*}(w)+\kappa-1$ and
_unsafe_ otherwise. Note that for a safe element $w$, it holds that
$\pi(w)\leq 2^{p(w)+1}\leq 2^{\kappa}\cdot 2^{p^{*}(w)}\leq
2^{\kappa}\cdot\pi^{*}(w)=O(r)\cdot\pi^{*}(w)$, i.e., its position on the list
of Dlm is at most $O(r)$ times greater than on the list of Off.

######  Lemma 3.6.

Assume that the position of an element $w$ on the list of Dlm increases by
$1$. Then, $\Delta\Phi_{w}+\Delta\Psi_{w}\leq 0$ if $w$ was safe before the
movement and $\Delta\Phi_{w}+\Delta\Psi_{w}\leq 3\beta$ otherwise.

######  Proof 3.7.

By $\pi(w)=2^{p(w)}+q(w)$ and
$\pi^{\prime}(w)=\pi(w)+1=2^{p^{\prime}(w)}+q^{\prime}(w)$ we denote the
positions of $w$ before and after the movement, respectively.

Assume first that $w$ was safe before the movement. As $p^{\prime}(w)\leq
p(w)+1\leq p^{*}(w)+\kappa$, $\Delta\Phi_{z}=\alpha\cdot b(z)-\alpha\cdot
b(z)=0$. Furthermore, either $p^{\prime}(w)=p(w)$, and then $\Delta\Psi_{w}=0$
trivially, or $p^{\prime}(w)=p(w)+1$, and then $q^{\prime}(w)=0$. In the
latter case $\Delta\Psi_{w}=2\beta\cdot q^{\prime}(z)-0=0$ as well. This shows
the first part of the lemma.

Assume now that $w$ was unsafe ($p(w)\geq p^{*}(w)+\kappa$) before the
movement. We consider two cases.

  * •

$p(w)=p^{*}(w)+\kappa$ and $p^{\prime}(w)=p(w)+1$.

It means that $q(w)=2^{p(w)}-1$ and $q^{\prime}(w)=0$. Then,

$\displaystyle\Delta\Phi_{w}$
$\displaystyle=\beta\cdot\pi^{\prime}(z)-\gamma\cdot\beta(z)-\alpha\cdot\beta(z)\leq\beta\cdot\pi^{\prime}(z)=\beta\cdot
2^{p^{\prime}(w)}=2\beta\cdot 2^{p(w)}$ and $\displaystyle\Delta\Psi_{w}$
$\displaystyle=2\beta\cdot q^{\prime}(z)-2\beta\cdot
q(z)=-2\beta\cdot(2^{p(w)}-1)=-2\beta\cdot 2^{p(w)}+2\beta.$

That is, the large growth of $\Phi_{w}$ is compensated by the drop of
$\Psi_{w}$, i.e, $\Delta\Phi_{w}+\Psi_{w}\leq 2\beta$.

  * •

$p(w)>p^{*}(w)+\kappa$ or $p^{\prime}(w)=p(w)$.

In such case, there is no case change in the definition of $\Phi_{w}$, i.e,

$\Delta\Phi_{w}=\begin{cases}\alpha\cdot b(w)-\alpha\cdot b(w)=0&\text{if
$p(w)\leq p^{*}(w)+\kappa$,}\\\ (\beta\cdot\pi^{\prime}(w)-\gamma\cdot
b(w))-(\beta\cdot\pi(w)-\gamma\cdot b(w))=\beta&\text{otherwise.}\end{cases}$

Furthermore, as $q^{\prime}(w)\leq q(w)+1$, $\Delta\Psi(z)=2\beta\cdot
q^{\prime}(w)-2\beta\cdot q(w)\leq 2\beta$. Together,
$\Delta\Phi_{w}+\Delta\Psi_{w}\leq\beta+2\beta=3\beta$.

######  Lemma 3.8.

Assume that the position of an element $w$ on the list of Off increases by
$1$. Then, $\Delta\Phi_{w}\leq 0$ and $\Delta\Psi_{w}\leq 0$.

######  Proof 3.9.

Note that $p^{*}(w)$ may be either unchanged (in which case the values of
$\Phi_{w}$ and $\Psi_{w}$ remain intact) or it may be incremented. We analyze
the latter case.

By (3), the definition of $\Phi_{w}$, the value of $\Phi_{w}$ may change only
if $p^{*}(w)$ is incremented from $p(w)+\kappa-1$ to $p(w)+\kappa$. In such
case,

$\displaystyle\Delta\Psi_{w}$ $\displaystyle=\alpha\cdot
b(w)-\beta\cdot\pi(w)+\gamma\cdot b(w)$
$\displaystyle\leq(\alpha+\gamma-\beta)\cdot\pi(w)$ (by section 3)
$\displaystyle\leq 0.$ (by Fact 1)

By (4), the definition of $\Psi_{w}$, the value of $\Psi_{w}$ may change only
if $p^{*}(w)$ is incremented from $p(w)+\kappa$ to $p(w)+\kappa+1$. In such
case, $\Delta\Psi_{w}=-2\beta\cdot q(w)\leq 0$.

##  4 Analysis in the static scenario

As described in subsection 3.1, in this part, we focus on the amortized cost
of Dlm in the first stage of a step, i.e., where Dlm and Off both pay their
access costs and then Dlm reorders its list.

######  Lemma 4.1.

Whenever Dlm executes operation ${\textsc{fetch}}(z)$, it holds that
$\Delta\textnormal{{Dlm}}+\Delta\Psi+\sum_{w\neq z}\Delta\Phi_{w}\leq
2\cdot\pi(z)$.

######  Proof 4.2.

As defined in Routine 1, the cost of operation ${\textsc{fetch}}(z)$ is
$\Delta\textnormal{{Dlm}}=\pi(z)-1<\pi(z)$. We first analyze the potential
changes of elements from set $K$ of $\pi(z)-1$ elements that originally
preceded $z$.

Let $K^{\prime}=\\{w\in K\;\mid\;\pi^{*}(w)\leq 2^{p(z)-\kappa+1}\\}$. Observe
that any $w\in K\setminus K^{\prime}$ satisfies
$\pi^{*}(w)>2^{p(z)-\kappa+1}$, which implies $p^{*}(w)\geq p(z)-\kappa+1\geq
p(w)-\kappa+1$, and thus $w$ is safe. Thus, among elements of $K$, only
elements from $K^{\prime}$ can be unsafe. By 3.6,

$\displaystyle\sum_{w\in K}(\Delta\Phi_{w}+\Delta\Psi_{w})$
$\displaystyle\leq\sum_{w\in K^{\prime}}(\Delta\Phi_{w}+\Delta\Psi_{w})\leq
3\beta\cdot|K^{\prime}|=3\beta\cdot 2^{p(z)-\kappa+1}$ $\displaystyle\leq
2^{p(z)}\leq\pi(z).$ $\displaystyle(\text{by
\lx@cref{creftype~refnum}{fact:constants}})$

As the only elements that may change their budgets are $z$ and elements from
$K$, we have $\Delta\textnormal{{Dlm}}+\Delta\Psi+\sum_{w\neq
z}\Delta\Phi_{w}=\Delta\textnormal{{Dlm}}+\sum_{w\in
K}\Delta\Psi_{w}+\Delta\Psi_{z}+\sum_{w\in K}\Delta\Phi_{w}\leq
2\cdot\pi(z)+\Delta\Psi_{z}\leq 2\cdot\pi(z)$. The last inequality follows as
$\Psi_{z}$ drops to $0$ when $z$ is moved to the list front.

Now we may split the cost of Dlm in a single step into parts incurred by Lines
2–2 and Lines 2–2, and bound them separately.

######  Lemma 4.3.

Whenever Dlm executes Lines 2–2 of Algorithm 2,
$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq 0$.

######  Proof 4.4.

Let $z$ be the element moved in algorithm 2. algorithm 2 guarantees that
$b(z)\geq\pi(z)$ and section 3 implies $b(z)\leq(3/2)\cdot\pi(z)$. The value
of $\Phi_{z}$ before the movement is then

$\displaystyle\Phi_{z}$ $\displaystyle\geq\min\\{\alpha\cdot
b(z),\,\beta\cdot\pi(z)-\gamma\cdot b(z)\\}$
$\displaystyle\geq\min\left\\{\alpha\,,\beta-(3/2)\cdot\gamma\right\\}\cdot\pi(z)$
$\displaystyle\geq 2\cdot\pi(z).$ (by Fact 1)

When $z$ is moved to the list front, potential $\Phi_{z}$ drops to $0$, and
thus $\Delta\Phi_{z}\leq-2\cdot\pi(z)$. Hence, using 4.1,
$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq
2\cdot\pi(z)+\Delta\Phi_{z}\leq 0$.

######  Lemma 4.5.

Fix any step and consider its first part, where Dlm pays for its access and
movement costs, whereas Off pays for its access cost. Then,
$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq(3+\alpha)\cdot
2^{\kappa+1}\cdot\Delta\textnormal{{Off}}=O(r)\cdot\Delta\textnormal{{Off}}$.

######  Proof 4.6.

Let $R=\\{x,y_{1},\dots,y_{s-1}\\}$ be the requested set, where $s\leq r$ and
$\pi(x)<\pi(y_{i})$ for any $i\in[s-1]$. Let $\Phi_{x}$ denote the value of
the potential just before the request. It suffices to analyze the amortized
cost of Dlm in Lines 2–2 as the cost in the subsequent lines is at most $0$ by
4.3. In these lines:

  * •

Dlm pays $\pi(x)$ for the access.

  * •

Dlm performs the operation ${\textsc{fetch}}(x)$, whose amortized cost is, by
4.1, at most $2\cdot\pi(x)-\Phi_{x}$.

  * •

The budget of $y_{i}$ grows by $\Delta b(y_{i})=\pi(x)/s$ for each
$i\in[s-1]$. As these elements do not move (within Lines 2–2),
$\Delta\Psi_{y_{i}}=0$.

Thus, we obtain

$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq
3\cdot\pi(x)-\Phi_{x}+\sum_{i\in[s-1]}\Delta\Phi_{y_{i}}.$ (5)

As elements $y_{i}$ do not move (within Lines 2–2)), the change in
$\Phi_{y_{i}}$ can be induced only by the change in the budget of $y_{i}$. Let
$u\in R$ be the element with the smallest position on the list of Off, i.e.,
$\Delta\textnormal{{Off}}=\pi^{*}(u)$. We consider three cases.

  * •

$p(x)\leq p^{*}(u)+\kappa$.

Then $\pi(x)\leq 2^{p(x)+1}\leq 2^{\kappa+1}\cdot 2^{p^{*}(u)}\leq
2^{\kappa+1}\cdot\pi^{*}(u)=2^{\kappa+1}\cdot\Delta\textnormal{{Off}}$. Note
that $\sum_{i\in[s-1]}\Delta\Phi_{y_{i}}\leq\sum_{i\in[s-1]}\alpha\cdot\Delta
b(y_{i})=(s-1)\cdot\alpha\cdot\pi(x)/s<\alpha\cdot\pi(x)$. By 3.4,
$\Phi_{x}\geq 0$, and thus using (5),

$\displaystyle\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi$
$\displaystyle<3\cdot\pi(x)+\alpha\cdot\pi(x)\leq(3+\alpha)\cdot
2^{\kappa+1}\cdot\Delta\textnormal{{Off}}.$

  * •

$p(x)\geq p^{*}(u)+\kappa+1$ and $u=x$.

In this case, $\Phi_{x}\geq\beta\cdot\pi(x)-\gamma\cdot
b(x)\geq(\beta-(3/2)\cdot\gamma)\cdot\pi(x)$ (cf. section 3). By plugging this
bound to (5), we obtain

$\displaystyle\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi$
$\displaystyle\leq
3\cdot\pi(x)+(\beta-(3/2)\cdot\gamma)\cdot\pi(x)+\alpha\cdot\pi(x)\leq 0,$

where the last inequality follows as $\beta\geq 3+(3/2)\cdot\gamma+\alpha$ by
Fact 1.

  * •

$p(x)\geq p^{*}(u)+\kappa+1$ and $u=y_{j}$ for some $j\in[s-1]$.

Recall that $\pi(x)<\pi(y_{i})$, and thus $p(y_{j})\geq p(x)$. Hence,
$p(y_{j})\geq p^{*}(y_{j})+\kappa+1$. In such a case,

$\displaystyle\sum_{i\in[s-1]}\Delta\Phi_{y_{i}}$
$\displaystyle=\Delta\Phi_{y_{j}}+\sum_{i\in[s-1]\setminus\\{j\\}}\Delta\Phi_{y_{i}}$
$\displaystyle\leq-\gamma\cdot\Delta
b(y_{j})+\sum_{i\in[s-1]\setminus\\{j\\}}\alpha\cdot\Delta b(y_{i})$
$\displaystyle=-\gamma\cdot\pi(x)/s+(s-2)\cdot\alpha\cdot\pi(x)/s$
$\displaystyle<(\alpha-\gamma/r)\cdot\pi(x).$ (as $s\leq r$)

Plugging the bound above and $\Phi_{x}\geq 0$ to (5) yields

$\Delta\textnormal{{Dlm}}+\Delta\Phi+\Delta\Psi\leq(3+\alpha-\gamma/r)\cdot\pi(x)\leq
0,$

where the last inequality again follows by Fact 1.

######  Theorem 4.7.

Dlm is $O(r)$-competitive in the static scenario.

######  Proof 4.8.

Fix any input $\mathcal{I}$ ad any offline solution Off that maintains a fixed
permutation. For any step $t$, let $\Phi^{t}$ and $\Psi^{t}$ denote the total
potentials right after step $t$, while $\Phi^{0}$ and $\Psi^{0}$ be the
initial potentials. By 4.5,

$\displaystyle\textnormal{{Dlm}}_{t}(\mathcal{I})$
$\displaystyle+\Phi^{t}+\Psi^{t}-\Phi^{t-1}-\Psi^{t-1}=O(r)\cdot\textnormal{{Off}}_{t}(\mathcal{I}),$
(6)

where $\textnormal{{Dlm}}_{t}(\mathcal{I})$ and
$\textnormal{{Off}}_{t}(\mathcal{I})$ denote the costs of Dlm and Off in step
$t$, respectively. By summing (6) over all $m$ steps of the input, we obtain
$\textnormal{{Dlm}}(\mathcal{I})+\Phi^{m}+\Psi^{m}-\Phi^{0}-\Psi^{0}\leq
O(r)\cdot\textnormal{{Off}}(\mathcal{I})$. As $\Phi^{m}+\Psi^{m}\geq 0$,

$\textnormal{{Dlm}}(\mathcal{I})\leq
O(r)\cdot\textnormal{{Off}}(\mathcal{I})+\Phi^{0}+\Psi^{0}.$

Note that the initial potentials might be non-zero as in the static scenario
Off starts in its permutation which might be different from $\pi_{0}$. That
said, both initial potentials can be universally upper-bounded by the amount
independent of $\mathcal{I}$, and thus Dlm is $O(r)$-competitive.

##  5 Analysis in the dynamic scenario

To analyze Dlm in the dynamic scenario, we first establish an offline
approximation of Opt that could be handled using our potential functions.

We say that an algorithm is _move-to-front based ( Mtf-based)_ if, in response
to request $R$, it chooses exactly one of the elements from $R$, brings it to
the list front, and does not perform any further actions. We denote the class
of all such (offline) algorithms by Mtfb. The proof of the following lemma can
be found in the appendix.

######  Lemma 5.1.

For any input $\mathcal{I}$, there exists an (offline) algorithm
$\textnormal{{Off}}^{*}\in\textnormal{{Mtfb}}$, such that
$\textnormal{{Off}}^{*}(\mathcal{I})\leq
4\cdot\textnormal{{Opt}}(\mathcal{I})$.

We now analyze the second stage of a step, where an offline algorithm Off from
the class Mtfb reorders its list.

######  Lemma 5.2.

Assume $\textnormal{{Off}}\in\textnormal{{Mtfb}}$. Fix any step and consider
its second stage, where Off moves some element $z$ to the list front. Then,
$\Delta\Phi+\Delta\Psi=O(r^{2})\cdot\Delta\textnormal{{Off}}$.

######  Proof 5.3.

We may assume that initially $\pi^{*}(z)\geq 2$, as otherwise there is no
change in the list of Off and the lemma follows trivially.

Apart from element $z$, the only elements that change their positions are
elements that originally preceded $z$: their positions are incremented. By
3.8, the potential change associated with these elements is non-positive.

Thus, $\Delta\Phi+\Delta\Psi\leq\Delta\Phi_{z}+\Delta\Psi_{z}$. Element $z$ is
transported by Off from position $\pi^{*}(z)$ to position $1$, i.e.,
$\Delta\textnormal{{Off}}=\pi^{*}(z)-1\geq\pi^{*}(z)/2$ as we assumed
$\pi^{*}(z)\geq 2$. Thus, to show the lemma it suffices to show that
$\Delta\Phi_{z}=O(r^{2})\cdot\pi^{*}(z)$ and
$\Delta\Psi_{z}=O(r^{2})\cdot\pi^{*}(z)$. We bound them separately.

  * •

Note that $p^{*}(z)$ may only decrease. If initially $p^{*}(z)\leq
p(z)-\kappa-1$, then $\Phi_{z}=\beta\cdot\pi(z)-\gamma\cdot b(z)$ before and
after the movement of $z$, and thus $\Delta\Phi_{z}=0$. Otherwise,
$p^{*}(z)\geq p(z)-\kappa$, which implies $\pi(z)<2^{p(z)+1}\leq
2^{\kappa+1}\cdot 2^{p^{*}(z)}\leq 2^{\kappa+1}\cdot\pi^{*}(z)$. In such a
case,

$\Delta\Phi_{z}\leq\beta\cdot\pi(z)-\gamma\cdot b(z)-\alpha\cdot
b(z)\leq\beta\cdot\pi(z)\leq\beta\cdot
2^{\kappa+1}\cdot\pi^{*}(z)=O(r^{2})\cdot\pi^{*}(z).$

  * •

Similarly, if initially $p^{*}(z)\leq p(z)-\kappa$, then $\Psi_{z}=2\beta\cdot
q(z)$ before and after the movement of $z$, and thus $\Delta\Psi_{z}=0$.
Otherwise, $p^{*}(z)\geq p(z)-\kappa+1$ and which implies
$\pi(z)<2^{p(z)+1}\leq 2^{\kappa}\cdot 2^{p^{*}(z)}\leq
2^{\kappa}\cdot\pi^{*}(z)$. In such a case

$\Delta\Psi_{z}\leq 2\beta\cdot q(z)-0\leq 2\beta\cdot\pi(z)\leq 2\beta\cdot
2^{\kappa}\cdot\pi^{*}(z)=O(r^{2})\cdot\pi^{*}(z).$

######  Theorem 5.4.

Dlm is strictly $O(r^{2})$-competitive in the dynamic scenario.

######  Proof 5.5.

The argument here is the same as for Theorem 4.7, but this time we sum the
guarantees provided for the first stage of a step (4.5) and for the second
stage of a step (5.2). This shows that for any offline algorithm
$\textnormal{{Off}}\in\textnormal{{Mtfb}}$ and any input $\mathcal{I}$ it
holds that

$\textnormal{{Dlm}}(\mathcal{I})\leq
O(r^{2})\cdot\textnormal{{Off}}(\mathcal{I})+\Phi^{0}+\Psi^{0}.$ (7)

For the dynamic scenario, the initial permutations of Dlm and Off are equal,
and hence the initial potential $\Phi^{0}+\Psi^{0}$ is zero. As (7) holds
against arbitrary $\textnormal{{Off}}\in\textnormal{{Mtfb}}$, it holds also
against $\textnormal{{Off}}^{*}$ which is the $4$-approximation of Opt (cf.
5.1). This implies that

$\textnormal{{Dlm}}(\mathcal{I})\leq
O(r^{2})\cdot\textnormal{{Off}}^{*}(\mathcal{I})\leq O(4\cdot
r^{2})\cdot\textnormal{{Opt}}(\mathcal{I}),$

which concludes the proof.

##  6 Final remarks

In this paper, we studied achievable competitive ratios for the online Mssc
problem. We closed the gaps for deterministic polynomial-time static scenarios
and tighten the gaps for deterministic dynamic scenarios. Still, some
intriguing open questions remain, e.g., the best randomized algorithm for the
dynamic scenario has a competitive ratio of $O(r^{2})$, while the lower bound
is merely a constant.

Another open question concerns a generalization of the MSSC problem where each
set $R_{t}$ comes with a covering requirement $k_{t}$ and an algorithm is
charged for the positions of the first $k_{t}$ elements from $R_{t}$ on the
list (see, e.g., [3]). The only online results so far are achieved in the
easiest, learning scenario [13].

## References

  * [1] Eugene Agichtein, Eric Brill, and Susan T. Dumais.  Improving web search ranking by incorporating user behavior information.  SIGIR Forum, 52(2):11–18, 2018.  doi:10.1145/3308774.3308778.
  * [2] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of Computing Systems, 8(1):121–164, 2012.  doi:10.4086/toc.2012.v008a006.
  * [3] Nikhil Bansal, Jatin Batra, Majid Farhadi, and Prasad Tetali.  Improved approximations for min sum vertex cover and generalized min sum set cover.  In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 998–1005. SIAM, 2021.  doi:10.1137/1.9781611976465.62.
  * [4] Amotz Bar-Noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, and Tami Tamir.  On chromatic sums and distributed resource allocation.  Information and Computation, 140(2):183–202, 1998.  doi:10.1006/inco.1997.2677.
  * [5] Shai Ben-David, Allan Borodin, Richard M. Karp, Gabor Tardos, and Avi Wigderson.  On the power of randomization in online algorithms.  Algorithmica, 11(1):2–14, 1994.  doi:10.1007/BF01294260.
  * [6] Marcin Bienkowski and Marcin Mucha.  An improved algorithm for online reranking.  In Proc. 37th AAAI Conference on Artificial Intelligence, pages 6815–6822, 2023.  doi:doi.org/10.1609/aaai.v37i6.25835.
  * [7] Avrim Blum and Carl Burch.  On-line learning and the metrical task system problem.  Machine Learning, 39(1):35–58, 2000.  doi:10.1023/A:1007621832648.
  * [8] Allan Borodin and Ran El-Yaniv.  Online Computation and Competitive Analysis.  Cambridge University Press, 1998.
  * [9] Mahsa Derakhshan, Negin Golrezaei, Vahideh H. Manshadi, and Vahab S. Mirrokni.  Product ranking on online platforms.  In Proc. 21st ACM Conference on Economics and Computation (EC), page 459. ACM, 2020.  doi:10.1145/3391403.3399483.
  * [10] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar.  Rank aggregation methods for the web.  In Proc. 10th Int. World Wide Web Conference (WWW), pages 613–622. ACM, 2001.  doi:10.1145/371920.372165.
  * [11] Uriel Feige, László Lovász, and Prasad Tetali.  Approximating min sum set cover.  Algorithmica, 40(4):219–234, 2004.  doi:10.1007/s00453-004-1110-5.
  * [12] Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas.  The online min-sum set cover problem.  In Proc. 47th Int. Colloq. on Automata, Languages and Programming (ICALP), pages 51:1–51:16, 2020.  doi:10.4230/LIPIcs.ICALP.2020.51.
  * [13] Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, and Stratis Skoulakis.  Efficient online learning of optimal rankings: Dimensionality reduction via gradient descent.  In Proc. 33rd Annual Conf. on Neural Information Processing Systems (NeurIPS), pages 7816–7827, 2020.
  * [14] Shahin Kamali.  Online list update.  In Encyclopedia of Algorithms, pages 1448–1451. Springer, 2016\.  doi:10.1007/978-1-4939-2864-4_266.
  * [15] Nick Littlestone and Manfred K. Warmuth.  The weighted majority algorithm.  Information and Computation, 108(2):212–261, 1994.  doi:10.1006/inco.1994.1009.
  * [16] Daniel D. Sleator and Robert E. Tarjan.  Amortized efficiency of list update and paging rules.  Communications of the ACM, 28(2):202–208, 1985.  doi:10.1145/2786.2793.

##  Appendix A Tightness of the analysis

In this section, we show that our analysis for Dlm is tight by presenting an
input sequence $\mathcal{I}$ for which
$\textnormal{{Dlm}}(\mathcal{I})\geq\Omega(r^{2})\cdot\textnormal{{Opt}}(\mathcal{I})$.
We show that such a bound holds even for the parameterized version of Dlm that
we describe below.

Recall that when Dlm processes a request $\\{x,y_{1},y_{2},\dots,y_{s-1}\\}$
(where $\pi(x)<\pi(y_{i})$), it increases the budgets of all elements $y_{i}$
by $\ell/s$ (cf. algorithm 2 of Algorithm 2). There, $\ell$ is the initial
value of $\pi(x)$ right before the request. If we changed $s$ to $r$, the
analysis of Dlm would be essentially the same, with the disadvantage that then
Dlm would need to know $r$ upfront.

One may wonder whether a better ratio could be achieved by simply changing the
denominator of $r$ to another value. This motivates the following
parameterization of Dlm, called $\textnormal{{Dlm}}_{c}$. For a positive
integer $c$, $\textnormal{{Dlm}}_{c}$ is defined as Dlm, but we replace the
assignment in algorithm 2 of Algorithm 2 with

$b(y_{i})\leftarrow b(y_{i})+\ell/c.$

For our lower bound, we make an additional assumption: we assume that if $k>1$
elements have budgets exceeding their current positions (cf. Lines 2–2 of
Algorithm 2), then $\textnormal{{Dlm}}_{c}$ fetches them to the first $k$
positions preserving their relative order.

######  Theorem A.1.

For any positive integer $c$, the competitive ratio of
$\textnormal{{Dlm}}_{c}$ in the dynamic scenario is $\Omega(r^{2})$.

In our construction, we set the number of elements $n$ to be $n=r^{2}+c\cdot
r$. The adversary employs the following play consisting of $c+1$ requests,
where each request contains the last $r$ elements in the current permutation
of $\textnormal{{Dlm}}_{c}$. We call such play a _phase_.

######  Lemma A.2.

Assume that, at some time, the budgets of all elements are zero. Let $A$ be
the set of the last $c+r$ elements on the list of $\textnormal{{Dlm}}_{c}$.
After $\textnormal{{Dlm}}_{c}$ serves the phase:

  * •

the budgets of all elements are again zero,

  * •

the first $c+r$ positions contain elements of $A$ shifted cyclically, and

  * •

all list elements not in $A$ increase their positions by $c+r$.

Furthermore, the cost of $\textnormal{{Dlm}}_{c}$ in such a phase is at least
$(c+r)\cdot(n-r)$.

######  Proof A.3.

We name elements of set $A$ as
$A=\\{a_{1},a_{2},\dots,a_{c+1},b_{1},b_{2},\dots b_{r-1}\\}$. Due to each of
$c+1$ requests, Alg fetches an element $a_{i}$ from position $n-r+1$ to the
list front and increases budgets of all elements $b_{j}$ by $(n-r+1)/c$.
Within the first $c$ requests, these budgets are at most
$c\cdot(n-r+1)/c=n-r+1$, and are thus smaller than the positions of the
corresponding elements $b_{j}$. However, after the $(c+1)$-th request, the
budget of any element $b_{j}$ will become equal to

$(c+1)\cdot\frac{n-r+1}{c}\geq(c+1)\cdot\frac{n-r}{c}=n+\frac{r^{2}-r}{c}\geq
n.$

Therefore, all elements $b_{1},b_{2},\dots,b_{r-1}$ are fetched to the list
front, and their budgets are reset to zero. (The budgets of all remaining
elements are always zero within the phase.) Once the phase ends, the list
front contains elements $b_{1},b_{2},\dots,b_{r-1},a_{1},a_{2},\dots,a_{c+1}$,
in this order.

It remains to lower-bound the cost of $\textnormal{{Dlm}}_{c}$ in a phase. We
neglect its access cost; its reordering cost consists of fetching $c+r$
elements, each from position $n-r+1$ or further, i.e., its total cost is at
least $(c+r)\cdot(n-r)$.

######  Proof A.4 (Proof of Theorem A.1).

Consider an input sequence $\mathcal{I}$ consisting of $m$ phases, where $m$
is a large number. As $n$ is divisible by $c+r$, we can partition all list
elements into $r$ disjoint sets $A_{1},A_{2},\ldots,A_{r}$, each of size
$c+r$, that will be requested in the cyclic order in the consecutive phases of
$\mathcal{I}$.

We bound $\textnormal{{Opt}}(\mathcal{I})$ by presenting an offline solution
Off for $\mathcal{I}$ with a small cost. Let $A^{\prime}_{i}$ contain every
$(r-1)$-th element from the original ordering of $A_{i}$, i.e.,
$|A^{\prime}_{i}|=\lfloor|A_{i}|/(r-1)\rfloor=\lfloor(c+r)/(r-1)\rfloor$. Let
$A^{*}=\bigcup_{i=1}^{r}A^{\prime}_{i}$. At the very beginning, Off moves all
elements from $A^{*}$ to the first
$|A^{*}|=r\cdot\lfloor(c+r)/(r-1)\rfloor\leq 2c+3r$ positions. The cost of
this operation becomes negligible in comparison to the remaining cost for a
sufficiently large number $m$ of phases. Throughout the whole input
$\mathcal{I}$, Off will keep elements of $A^{*}$ on the first $|A^{*}|$
positions, but it will change their relative order as discussed below.

Consider now any phase, in which elements from $A_{i}$ are requested. At its
beginning, by A.2, elements of $A_{i}$ are in the cyclically shifted original
order. Hence, $A^{*}$ contains one element $x^{*}$ among those that $A_{i}$
has now at the last $r-1$ positions of the list of $\textnormal{{Dlm}}_{c}$.
These $r-1$ elements are present in all requested sets of a phase. To serve
them, before the phase starts, Off fetches $x^{*}$ to the first position.
Then, its cost within a phase is at most $|A^{*}|-1\leq 2c+3r-1$ for
reordering and $c+1$ for accesses, i.e., $3c+3r$ in total.

Recall that by A.2, the cost of $\textnormal{{Dlm}}_{c}$ in a phase is at
least $(c+r)\cdot(n-r)$. Hence, for each phase, the
$\textnormal{{Dlm}}_{c}$-to-Off ratio is

$\displaystyle\frac{\textnormal{{Dlm}}_{c}}{\textnormal{{Opt}}}$
$\displaystyle\geq\frac{(c+r)\cdot(n-r)}{3c+3r}=\frac{n-r}{3}\geq\frac{r^{2}}{3}.$

Summing over all phases yields the desired lower bound.

##  Appendix B Omitted proofs

######  Proof B.1 (Proof of 5.1).

Based on the actions of Opt on $\mathcal{I}=(\pi_{0},R_{1},\ldots,R_{m})$, we
may create an input
$\mathcal{J}=(\pi_{0},R_{1}^{\prime},\ldots,R_{m}^{\prime})$ where
$R_{i}^{\prime}$ is a singleton set containing exactly the element from
$R_{i}$ that Opt has nearest to the list front.

Clearly, $\textnormal{{Opt}}(\mathcal{J})\leq\textnormal{{Opt}}(\mathcal{I})$.
Note that $\mathcal{J}$ is an instance of the list update problem. Thus, if we
take an algorithm Mtf for the list update problem (which brings the requested
element to the list front), then it holds that
$\textnormal{{Mtf}}(\mathcal{J})\leq 4\cdot\textnormal{{Opt}}(\mathcal{J})$
[16]. (The result of [16] shows the competitive ratio of $2$, but the list
update model ignores reordering costs. However, for Mtf the reordering costs
are equal to access costs minus $1$ and hence, taking them into account at
most doubles the competitive ratio.)

Let now $\textnormal{{Off}}^{*}$ be an offline algorithm that, on input
$\mathcal{I}$, performs the same list reordering as
$\textnormal{{Mtf}}(\mathcal{J})$. Clearly,
$\textnormal{{Off}}^{*}\in\textnormal{{Mtfb}}$. While the reordering cost of
$\textnormal{{Off}}^{*}$ on $\mathcal{I}$ coincide with that of Mtf on
$\mathcal{J}$, its access cost can be only smaller. Thus,
$\textnormal{{Off}}^{*}(\mathcal{I})\leq\textnormal{{Mtf}}(\mathcal{J})$.

Summing up, we obtain
$\textnormal{{Off}}^{*}(\mathcal{I})\leq\textnormal{{Mtf}}(\mathcal{J})\leq
4\cdot\textnormal{{Opt}}(\mathcal{J})\leq
4\cdot\textnormal{{Opt}}(\mathcal{I})$, which concludes the proof.


# Quantum master equation approach to heat transport in dielectrics and
semiconductors

Yamen Hamdouni  Physics department, Mentouri university, Constantine, Algeria
<EMAIL_ADDRESS>
###### Abstract

We report on the derivation of the heat transport equation for nonmetals using
a quantum Markovian master equation in Lindblad form. We first establish the
equations of motion describing the time variation of the on-site energy of
atoms in a one dimensional periodic chain that is coupled to a heat reservoir.
In the continuum limit, the Fourier law of heat conduction naturally emerges,
and the heat conductivity is explicitly obtained. It is found that the effect
of the heat reservoir on the lattice is described by a heat source density
that depends on the diffusion coefficients of the atoms. We show that the
Markovian dynamics is equivalent to the long wavelength approximation for
phonons, which is typical for the case of elastic solids. The high temperature
limit is shown to reproduce the classical heat conduction equation.

Keywords: open quantum systems, Markovian dynamics, heat transport

##  1 Introduction

Thermal conductivity in solids has various origins depending on whether they
are metals or nonmetals [1, 2]. In the former case, electrons are the main
carriers of heat. In semiconductors and dielectrics, however, phonons play the
crucial role in the process of heat transport. The study of these properties
has a significant importance especially in the use and the fabrication of many
devices that are based on these materials. The description of the dynamics of
atoms in solids usually relies on their fundamental symmetries such as lattice
periodicity, which has great consequences. Actually, phonons are merely the
quantized perturbations that propagate throughout the periodic lattice. In
their motion, phonons may undergo many interaction processes, leading to their
decay or relaxation. The latter fact affects significantly the phenomenon of
heat transport by phonons.

Generally speaking, heat conduction occurs when a non-zero gradient of the
temperature exists in the material. This process is phenomenologically well
described by the Fourier law which involves the so-called heat conductivity.
The study of this property is essentially based on the Focker-Planck equation,
where one is interested in the change of the distribution of the carriers in
space and time [3, 4]. In either case, whether for electrons or phonons, the
heat conductivity is derived using the relaxation time ansatz, which yields
for phonons a conductivity that is quite similar in its form to the
conductivity of gases.

In recent years, attention has been given to the quantum description of heat
transport in various physical systems [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16]. Apart from the need for new theoretical paradigms and elaborated
mathematical methods to handle the dynamics in many-body systems in a purely
quantum manner, this kind of problems has been associated with the development
of new experimental techniques that yield more precise and accurate
measurements at the atomic and molecular scale at low temperatures [17]. In
addition, several works have been devoted to the study of quantum
thermodynamics and quantum thermal machines [18, 19, 20, 21, 22, 23, 24], and
quantum control [25], where the laws of quantum mechanics come to play.
Besides, the question of how do classical laws of heat transport emerge from
the quantum ones is thus of fundamental importance.

The main aim of this paper is to approach the problem of heat transport in
nonmetals from the perspective of the theory of open quantum systems [26].
Indeed, given that we are dealing with a non-equilibrium problem [27], we
assume that the lattice is in contact with a heat reservoir and we propose to
study the lattice dynamics using the quantum master equation technique [28,
29]. The aim here is two-fold: First, we seek to derive the equations of
motion for the constituents of the discrete lattice on the atomic level, and
to draw conclusions regarding the way the energy decays and flows from one
site to another. Second, we treat the classical heat transport as a limiting
case of the discrete one by invoking the continuum limit, from which the heat
conductivity of the lattice may be obtained in a nontrivial manner. A natural
choice for the continuum limit is the Markovian approximation for the master
equation. The most general form of the latter has been found by Lindblad in
his seminal work [30, 31]. Practically, most of the Master equations used in
various fields may be reduced to the Lindblad form. We shall use the latter by
postulating a particular choice for the Lindblad operators that is best
adapted to Harmonic motion of the atoms in the lattice. It is worthwile to
notice here that the use of the master equation formalism has been adopted for
studying heat flow in spin chains by many authors.

The paper is organized as follows. In Sec. 2, we introduce the model and we
derive the equations of motion for the on-site energy. Section 3 is devoted to
the continuum limit, where we derive the classical heat transport equation,
and deduce the heat conductivity. There, we discuss the implication of the
Markovian approximation, and we study the high temperature limit. The paper is
ended with a brief conclusion.

##  2 Model and equations of motion

In nonmetallic materials, heat transport is mainly due to the out of
equilibrium dynamics of phonons. The contribution of electrons being
negligible compared to that of the phonons, we disregard the electronic
degrees of freedom of the atoms and, for the sake of simplicity, we restrict
ourselves to one dimension. Under these conditions, we model the system of
interest by the Hamiltonian:

$\hat{H}=\sum_{k=1}^{N}\frac{\hat{p}_{k}^{2}}{2m}+\left(\frac{1}{2}m\omega_{0}^{2}+\xi\right)\hat{x}_{k}^{2}-\xi\hat{x}_{k}\hat{x}_{k+1},$
(1)

where all the atoms are assumed identical (monoatomic chain) with the same
mass $m$. The frequency $\omega_{0}$ describes the local harmonic oscillator
potential in which each atom is immersed, whereas the parameter $\xi$, which
is essentially positive (i.e. $\xi>0$), represents the coupling constant
between neighboring atoms. The operators $\hat{x}_{k}$ and $\hat{p}_{k}$
satisfy the usual canonical commutation relations:

$[\hat{x}_{k},\hat{p}_{k^{{}^{\prime}}}]=i\hbar\delta_{kk^{{}^{\prime}}},\qquad[\hat{x}_{k},\hat{x}_{k^{{}^{\prime}}}]=0,\qquad[\hat{p}_{k},\hat{p}_{k^{{}^{\prime}}}]=0.$
(2)

In order to deal with the irreversible energy transport on the atomic scale,
we assume that the system is weakly coupled to a heat reservoir, whose size
and properties are not altered by the interaction with the lattice. This
causes energy exchange between the chain and the reservoir as well as heat
flow through the former until it reaches its equilibrium state. Furthermore,
we assume that the time scale at which the state of the lattice changes is
much longer than any time scale characterizing the reservoir. The latter
conditions lead to a Markovian-type dynamics that is well described by means
of a master equation in Lindblad form for the system’s reduced density matrix
$\hat{\rho}(t)$, which can be written in the Schrödinger picture as [30, 31]

$\frac{d\hat{\rho}(t)}{dt}=-\frac{i}{\hbar}[\hat{H},\hat{\rho}(t)]+\frac{1}{2\hbar}\sum_{\ell}([\hat{V}_{\ell}\hat{\rho}(t),\hat{V}_{\ell}^{\dagger}]+[\hat{V}_{\ell},\hat{\rho}(t)\hat{V}_{\ell}^{\dagger}]).$
(3)

The influence of the heat reservoir on the state of the lattice is encoded in
the Lindblad operators $\hat{V}_{\ell}$, which play a crucial role in the
theory of open quantum systems. In the Heisenberg picture, the dual evolution
equation for the operator $\hat{A}$ reads:

$\frac{d\hat{A}(t)}{dt}=\frac{i}{\hbar}[\hat{H},\hat{A}(t)]+\frac{1}{2\hbar}\sum_{\ell}([\hat{V}_{\ell}^{\dagger}[\hat{A}(t),\hat{V}_{\ell}]+[\hat{V}_{\ell}^{\dagger},\hat{A}(t)]\hat{V}_{\ell}]).$
(4)

We demand that the quantum equations of motion in the presence of dissipation
and damping be linear. This can be achieved by writing the Lindblad operators
in the form of linear combinations of the atoms coordinates and momenta
operators, namely:

$\hat{V}_{\ell}=\sum_{j=1}^{N}(a^{\ell}_{j}\hat{p}_{j}+b_{j}^{\ell}\hat{x}_{j}),\quad\hat{V}^{\dagger}_{\ell}=\sum_{j=1}^{N}(a^{\ell*}_{j}\hat{p}_{j}+b_{j}^{\ell*}\hat{x}_{j}).$
(5)

The complex numbers $a^{\ell}_{j}$ and $b_{j}^{\ell}$ serve to introduce the
quantum transport coefficients [28]:

$\displaystyle D_{x_{k}x_{j}}$ $\displaystyle=$
$\displaystyle\frac{\hbar}{2}{\rm
Re}\sum_{\ell}a^{\ell*}_{k}a^{\ell}_{j},\quad
D_{p_{k}p_{j}}=\frac{\hbar}{2}{\rm Re}\sum_{\ell}b^{\ell*}_{k}b^{\ell}_{j},$
(6) $\displaystyle D_{x_{k}p_{j}}$ $\displaystyle=$
$\displaystyle-\frac{\hbar}{2}{\rm
Re}\sum_{\ell}a^{\ell*}_{k}b^{\ell}_{j},\quad\lambda_{kj}=-{\rm
Im}\sum_{\ell}a^{\ell*}_{k}b^{\ell}_{j},$ (7) $\displaystyle\alpha_{kj}$
$\displaystyle=$ $\displaystyle-{\rm
Im}\sum_{\ell}a^{\ell*}_{k}a^{\ell}_{j},\qquad\eta_{kj}=-{\rm
Im}\sum_{\ell}b^{\ell*}_{k}b^{\ell}_{j},$ (8)

which enables us to rewrite the master equation (4) in the more explicit form:

$\displaystyle\frac{d\hat{A}}{dt}=\frac{i}{\hbar}[\hat{H},\hat{A}]+\frac{1}{2\hbar^{2}}\sum_{kj}\Biggl{\\{}(i\hbar\alpha_{kj}-2D_{x_{k}x_{j}})\Bigl{(}\\{\hat{A},\hat{p}_{k}\hat{p}_{j}\\}-2\hat{p}_{k}\hat{A}\hat{p}_{j}\Bigl{)}$
$\displaystyle+(i\hbar\eta_{kj}-2D_{p_{k}p_{j}})\Bigl{(}\\{\hat{A},\hat{x}_{k}\hat{x}_{j}\\}-2\hat{x}_{k}\hat{A}\hat{x}_{j}\Bigl{)}+(2D_{p_{k}x_{j}}+i\hbar\lambda_{jk})\times$
$\displaystyle\Bigl{(}\\{\hat{A},\\{\hat{p}_{j},\hat{x}_{k}\\}\\}-2(\hat{p}_{j}\hat{A}\hat{x}_{k}+\hat{x}_{k}\hat{A}\hat{p}_{j})\Bigl{)}-2\hbar\lambda_{jk}\Bigl{(}\\{\hat{A},\hat{p}_{j}\hat{x}_{k}\\}-2\hat{x}_{k}\hat{A}\hat{p}_{j}\Big{)}\Biggr{\\}}.$
(9)

In the above equation, $\\{\hat{A},\hat{B}\\}$ designates the anticommutator
of the operators $\hat{A}$ and $\hat{B}$; the corresponding expectation values
$\overline{A}$ and $\overline{AB}$ are defined by:

$\displaystyle\overline{A}(t)$ $\displaystyle=$ $\displaystyle{\rm
tr}(\hat{\rho}\hat{A}(t)),$ (10) $\displaystyle\overline{AB}(t)$
$\displaystyle=$ $\displaystyle\frac{1}{2}{\rm
tr}\Bigl{(}\hat{\rho}\\{\hat{A}(t),\hat{B}(t)\\}\Bigl{)},$ (11)

where ${\rm tr}(.)$ denotes the trace with respect to the lattice state.

Using the master equation (9), it can be shown that the evolution in time of
the expectation values of the bilinear terms involved in the lattice
Hamiltonian satisfy:

$\displaystyle\frac{d\overline{x_{k}^{2}}}{dt}=-2\lambda_{kk}\overline{x_{k}^{2}}+\frac{2\overline{p_{k}x_{k}}}{m}-2\sum_{j\neq
k}\lambda_{kj}\overline{x_{k}x_{j}}-2\sum_{j\neq
k}\alpha_{kj}\overline{x_{k}p_{j}}+2D_{x_{k}x_{k}},$ (12)
$\displaystyle\frac{d\overline{p_{k}^{2}}}{dt}=-2\lambda_{kk}\overline{p_{k}^{2}}-\left(m\omega_{0}^{2}+2\xi\right)\overline{x_{k}p_{k}}-2\sum_{j\neq
k}\lambda_{kj}\overline{p_{k}p_{j}}$ $\displaystyle+2\sum_{j\neq
k}[\eta_{kj}+\xi(\delta_{jk-1}+\delta_{jk+1})]\overline{p_{k}x_{j}}+2D_{p_{k}p_{k}},$
(13)
$\displaystyle\frac{d\overline{x_{k}x_{k+1}}}{dt}=-(\lambda_{kk}+\lambda_{k+1k+1})\overline{x_{k}x_{k+1}}+\frac{1}{m}(\overline{x_{k}p_{k+1}}+\overline{x_{k+1}p_{k}})$
$\displaystyle-\sum_{j\neq k}\lambda_{kj}\overline{x_{k+1}x_{j}}-\sum_{j\neq
k+1}\lambda_{k+1j}\overline{x_{k}x_{j}}$ $\displaystyle-\sum_{j\neq
k}\alpha_{kj}\overline{x_{k+1}p_{j}}-\sum_{j\neq
k+1}\alpha_{k+1j}\overline{x_{k}p_{j}}+2D_{x_{k}x_{k+1}},$ (14)

where we have assumed periodic boundary conditions $x_{1}=x_{N+1}$.

We shall define the expectation value of the on-site energy by

$E_{k}=\frac{\overline{p_{k}^{2}}}{2m}+\left(\frac{1}{2}m\omega_{0}^{2}+\xi\right)\overline{x_{k}^{2}}-\frac{\xi}{2}(\overline{x_{k}x_{k+1}}+\overline{x_{k}x_{k-1}}).$
(15)

The above quantity displays the non-local exchange nature of the energy,
namely via the coupling terms $\overline{x_{k}x_{k\pm 1}}$, leading thus to
energy transport through the lattice. Since all the atoms are identical, we
set $\lambda_{kk}=\lambda$ for all $k$, and by the antisymmetry character of
the coefficients $\alpha_{kj}$ and $\eta_{kj}$, we have $\alpha_{kj}=0$,
$\eta_{kj}=0$. The friction coefficients $\lambda_{kj}$, on the other hand are
symmetrical, and if we restrict the coupling to the nearest neighbors, we may
write them in the form:

$\lambda_{kj}=\gamma(\delta_{jk+1}+\delta_{jk-1}),\qquad{\rm for}\quad j\neq
k.$ (16)

Consequently,

$\displaystyle\frac{dE_{k}}{dt}$ $\displaystyle=$ $\displaystyle-2\lambda
E_{k}+\frac{D_{p_{k}p_{k}}}{m}+\left(m\omega_{0}^{2}+2\xi\right)D_{x_{k}x_{k}}-\xi(D_{x_{k}x_{k+1}}+D_{x_{k}x_{k-1}})$
(17) $\displaystyle-$
$\displaystyle\frac{\xi}{2m}\left(\overline{x_{k}p_{k+1}}+\overline{x_{k}p_{k-1}}-\overline{x_{k+1}p_{k}}-\overline{x_{k-1}p_{k}}\right)$
$\displaystyle-$
$\displaystyle\frac{\gamma}{m}(\overline{p_{k}p_{k+1}}+\overline{p_{k}p_{k-1}})-\gamma(m\omega_{0}^{2}+2\xi)(\overline{x_{k}x_{k+1}}+\overline{x_{k}x_{k-1}})$
$\displaystyle+$
$\displaystyle\frac{\gamma\xi}{2}\left(2\overline{x_{k}^{2}}+\overline{x_{k+1}^{2}}+\overline{x_{k-1}^{2}}\right).$

The right-hand side of equation (17) may be regarded as describing two-
particle and three-particle scattering processes, by which the lattice atoms
indirectly exchange energy through the environmental particles. Moreover, it
is worthwhile mentioning that the term

$\frac{\xi}{2m}\left(\overline{x_{k}p_{k+1}}+\overline{x_{k}p_{k-1}}-\overline{x_{k+1}p_{k}}-\overline{x_{k-1}p_{k}}\right)=a\nabla_{a}J_{k}$
(18)

is the algebraic sum of microscopic energy currents, which manifests itself in
the form of a discrete gradient of a local current $J_{k}$ on the lattice,
where $a$ is the lattice constant:

$\displaystyle a\nabla_{a}J_{k}=J_{k+1}-J_{k},$ (19) $\displaystyle
J_{k}=\frac{\xi}{2m}\left(\overline{x_{k-1}p_{k}}-\overline{x_{k}p_{k-1}}\right).$
(20)

For the sake of brevity, it is convenient to rewrite equation (17) as:

$\displaystyle\frac{dE_{k}}{dt}$ $\displaystyle=$ $\displaystyle-2\lambda
E_{k}+\frac{D_{p_{k}p_{k}}}{m}+\left(m\omega_{0}^{2}+2\xi\right)D_{x_{k}x_{k}}$
(21) $\displaystyle-$
$\displaystyle\xi(D_{x_{k}x_{k+1}}+D_{x_{k}x_{k-1}})+\mathcal{L}_{k},$

where

$\displaystyle\mathcal{L}_{k}$ $\displaystyle=$
$\displaystyle-\frac{\xi}{2m}\left(\overline{x_{k}p_{k+1}}+\overline{x_{k}p_{k-1}}-\overline{x_{k+1}p_{k}}-\overline{x_{k-1}p_{k}}\right)$
(22) $\displaystyle-$
$\displaystyle\frac{\gamma}{m}(\overline{p_{k}p_{k+1}}+\overline{p_{k}p_{k-1}})-\gamma(m\omega_{0}^{2}+2\xi)(\overline{x_{k}x_{k+1}}+\overline{x_{k}x_{k-1}})$
$\displaystyle+$
$\displaystyle\frac{\gamma\xi}{2}\left(2\overline{x_{k}^{2}}+\overline{x_{k+1}^{2}}+\overline{x_{k-1}^{2}}\right).$

The main contribution to $\mathcal{L}_{k}$ comes from the quantity displayed
in the first line of the above equation, whose characteristic time scale is of
the order of:

$t\sim\tau=\frac{1}{2\lambda}.$ (23)

This shows that the effect of any perturbation at site $k$ may extend beyond
the lattice constant $a$ over which the gradient in equation (18) is defined.
The range actually depends on the speed of propagation of the perturbation. We
shall return to this point later when we study the continuum limit. The
contribution of the remaining terms of $\mathcal{L}_{k}$ is generally small
because $\gamma\ll\lambda$; hence, they can be neglected in the continuum
limit (see bellow).

The lattice ultimately reaches its equilibrium state which is a Gibbs state at
the final temperature $T_{f}$. In this case the diffusion coefficients do not
depend on $k$ and are the same for all the atoms; we express this fact
symbolically by:

$\displaystyle D_{x_{k}x_{k}}$ $\displaystyle=$ $\displaystyle
D_{xx}(T_{f}),\qquad D_{p_{k}p_{k}}=D_{pp}(T_{f}),$ (24) $\displaystyle
D_{x_{k}x_{k-1}}$ $\displaystyle=$ $\displaystyle D_{x_{k}x_{k+1}}=D_{\rm
ex}(T_{f}).$ (25)

##  3 Continuum limit

The passage to the continuum limit should take into account the elasticity of
the lattice and the way energy flows from point to point, namely the position
dependence of the energy current. Hence when the lattice is out of
equilibrium, the energy should be dealt with as a continuously varying
quantity whose rate of change in time is tightly related to its spacial
variation, that is to its gradient. To this end let us introduce the quantity:

$u_{k}=\frac{E_{k}}{a}.$ (26)

In the continuum limit, $u_{k}$ becomes the energy density (i.e. energy by
unit of length) of the lattice, which will be denoted from here on by
$u(x,t)$:

$\frac{E_{k}}{a}\Bigl{|}_{x=ka}\rightarrow u(x,t).$ (27)

Let $b$ denote the range over which the gradient of the energy changes in the
homogeneous lattice during a time interval of the order of the decay time
constant:

$\tau=\frac{1}{2\lambda}.$ (28)

Therefore, the variation of the energy current density at site $k$ reads:

$\Delta\dot{u}_{k}=2\lambda(u_{k+[\frac{b}{a}]}-u_{k})-2\lambda(u_{k}-u_{k-[\frac{b}{a}]}),$
(29)

where $[x]$ designates the round value of $x$. The above variation captures
the change of the energy over the range $b$, including the contribution of the
nonlocal terms $\mathcal{L}_{k}$ in the continuum limit, where:

$\Delta\dot{u}_{k}\rightarrow 2\lambda b^{2}\frac{\partial^{2}u(x,t)}{\partial
x^{2}}.$ (30)

This is to be added to the decay of the energy during the time interval
$\tau$, which is described by the damping coefficient $2\lambda$. It follows
that in the continuum limit equation (21) turns into:

$\displaystyle\frac{\partial u(x,t)}{\partial t}=2\lambda
b^{2}\frac{\partial^{2}u(x,t)}{\partial x^{2}}-2\lambda u(x,t)+s(T_{f})$ (31)

where

$s(T_{f})=\frac{1}{a}\left[\frac{D_{pp}(T_{f})}{m}+\left(m\omega_{0}^{2}+2\xi\right)D_{xx}(T_{f})-2\xi
D_{\rm ex}(T_{f})\right].$ (32)

In fact equation (31) may be written as

$\frac{\partial u(x,t)}{\partial t}=\frac{\partial}{\partial x}\left(2\lambda
b^{2}\frac{\partial u(x,t)}{\partial x}\right)-2\lambda u(x,t)+s(T_{f}).$ (33)

This is the transient heat transport equation with source density $s(T_{f})$.
The corresponding heat current reads:

$J(x,t)=-2\lambda b^{2}\frac{\partial u(x,t)}{\partial x}.$ (34)

The latter can actually be put in the more familiar form:

$J(x,t)=-\kappa\frac{\partial T}{\partial x},$ (35)

where the thermal conductivity is given by:

$\kappa=2\lambda b^{2}C(T),$ (36)

with

$C(T)=\frac{\partial u(x,t)}{\partial T}$ (37)

being the heat capacity density of the lattice.

###  3.1 Range of propagation and the Markovian approximation

The derivation of the heat transport equation (33) and the thermal
conductivity $\kappa$ was based on a Markovian master equation. The obtained
results imply that the speed of propagation of heat is constant. We may thus
be tented to introduce the effective velocity

$v_{\rm eff}=\frac{b}{\tau},$ (38)

and to write the thermal conductivity in the form:

$\kappa=v_{\rm eff}bC(T).$ (39)

The latter form is exactly the same as that corresponding to thermal
conductivity in classical gases. This analogy, however, should be dealt with
more care, because we are actually dealing with phonon propagation. The study
of this phenomenon so far has been based on a Focker-Planck equation together
with the so-called relaxation time ansatz. The heat conductivity depends on
the phonons modes labeled by the wave vectors $\mathbf{q}$, and can be written
in one dimension as [4]:

$\kappa=\frac{1}{Na}\sum_{\mathbf{q}}v(\mathbf{q})r(\mathbf{q})\frac{\partial\epsilon(\mathbf{q},T)}{\partial
T},$ (40)

where $\epsilon(T,\mathbf{q})$ is the Bose-Einstein distribution,
$v(\mathbf{q})$ is the group velocity of mode $\mathbf{q}$ and
$r(\mathbf{q})=v(\mathbf{q})\tau(\mathbf{q})$ is the range of that mode, with
$\tau(\mathbf{q})$ being the corresponding relaxation time.

Therefore, the Markovian approximation combined with the elastic continuum
limit corresponds to constant group velocity of the phonons. This happens in
the long wavelength approximation for which only phonons of low frequencies do
contribute to the dynamics. Consider for instance the simplified model where
$\omega_{0}=0$. The modes frequencies are given by:

$\omega(\mathbf{q})=2\sqrt{\frac{\xi}{m}}|\sin(qa/2)|.$ (41)

In the long wavelength approximation, associated with the continuum limit, we
have $qa\ll 1$, meaning that:

$\omega(\mathbf{q})=a\sqrt{\frac{\xi}{m}}q,$ (42)

which yields a constant group velocity for all involved modes:

$v(\mathbf{q})=a\sqrt{\frac{\xi}{m}}.$ (43)

The latter is the velocity of sound in the lattice, and is the actual speed of
propagation of heat throughout the lattice. The range $b$ can thus be written
in the Markovian approximation as

$b=a\sqrt{\frac{\xi}{m}}\tau=\frac{a}{2\lambda}\sqrt{\frac{\xi}{m}},$ (44)

yielding the heat conductivity

$\kappa=\frac{a^{2}\xi}{2\lambda m}C(T).$ (45)

More explicitly, we can write:

$\displaystyle\frac{\partial u(x,t)}{\partial
t}=\left(\frac{a^{2}\xi}{2\lambda m}\right)\frac{\partial^{2}u(x,t)}{\partial
x^{2}}-2\lambda u(x,t)+s(T_{f}).$ (46)

Hence we conclude that the continuum heat transport equation emerges from the
combination of the long wavelength and the Markovian approximations when
applied to the quantum master equation.

###  3.2 High temperature limit

For simplicity we assume that $\gamma=0$; the case of $\gamma\neq 0$ is dealt
with in the appendix, and the outcome is essentially the same. The temperature
dependence of the source $s(T_{f})$ for arbitrary $T_{f}$ in the case of the
relaxation to the Gibbs equilibrium state is deduced from the diffusion
coefficients [28, 29]:

$\displaystyle D_{xx}$ $\displaystyle=$ $\displaystyle\frac{\hbar\lambda}{4\pi
m}\int_{-\pi}^{\pi}\frac{\coth\left(\frac{\hbar\omega(q)}{2k_{B}T_{f}}\right)}{\omega(q)}dq,$
(47) $\displaystyle D_{pp}$ $\displaystyle=$ $\displaystyle\frac{\hbar
m\lambda}{4\pi}\int_{-\pi}^{\pi}\coth\left(\frac{\hbar\omega(q)}{2k_{B}T_{f}}\right)\omega(q)dq,$
(48) $\displaystyle D_{\rm{ex}}$ $\displaystyle=$
$\displaystyle\frac{\hbar\lambda}{4\pi
m}\int_{-\pi}^{\pi}\frac{\coth\left(\frac{\hbar\omega(q)}{2k_{B}T_{f}}\right)}{\omega(q)}\cos(q)dq,$
(49)

where $k_{B}$ is the Boltzmann constant and

$\omega(q)=\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}\sin^{2}(q/2)}.$ (50)

At high temperatures, the above integrals simplify to:

$\displaystyle D_{xx}$ $\displaystyle=$ $\displaystyle\frac{\lambda
k_{B}T_{f}}{m\omega_{0}\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}},$ (51)
$\displaystyle D_{pp}$ $\displaystyle=$ $\displaystyle m\lambda k_{B}T_{f},$
(52) $\displaystyle D_{\rm{ex}}$ $\displaystyle=$ $\displaystyle\frac{\lambda
k_{B}T_{f}}{\xi\omega_{0}}\left(\frac{\omega_{0}^{2}+\frac{2\xi}{m}-\omega_{0}\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}{\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}\right).$
(53)

Taking into account these coefficients, it follows from equation (32) that:

$s(T_{f})=\frac{2\lambda k_{B}T_{f}}{a}.$ (54)

The heat transport equation becomes:

$\displaystyle\frac{\partial u(x,t)}{\partial
t}=\left(\frac{a^{2}\xi}{2\lambda m}\right)\frac{\partial^{2}u(x,t)}{\partial
x^{2}}-2\lambda\left(u(x,t)-\frac{k_{B}T_{f}}{a}\right).$ (55)

The latter result has a simple statistical explanation: At high temperature,
by the equipartition theorem, the equilibrium mean energy of the lattice is:

$\overline{U}=Nk_{B}T_{f}.$ (56)

Hence the equilibrium energy density reads:

$u_{\rm
eq}=\frac{Nk_{B}T_{f}}{Na}=\frac{k_{B}T_{f}}{a}=\frac{s(T_{f})}{2\lambda},$
(57)

which will be reached in the continuum limit once $\frac{\partial
u(x,t)}{\partial t}=\frac{\partial^{2}u(x,t)}{\partial x^{2}}=0$. Furthermore,
at such temperatures, the heat capacity density behaves classically and is
thus nearly constant:

$C(T)=\frac{k_{B}}{a},$ (58)

whereas the thermal conductivity takes the form:

$\kappa=\frac{ak_{B}\xi}{2\lambda m}=\frac{k_{B}\xi}{2\lambda\rho},$ (59)

where $\rho$ is the mass density of the lattice. The heat transport equation
simplifies further to

$\displaystyle\frac{\partial T(x,t)}{\partial
t}=\sigma\frac{\partial^{2}T(x,t)}{\partial
x^{2}}-2\lambda\left(T(x,t)-T_{f}\right),$ (60)

where $\sigma$ is the thermal diffusivity:

$\sigma=\frac{\kappa a}{k_{B}}=\frac{a^{2}\xi}{2\lambda m}.$ (61)

Obviously, the diffusivity is proportional to the coupling constant $\xi$ and
is inversely proportional to the atoms mass. The second term on the right-hand
side of equation (60) expresses the fact that the rate of change of
temperature between the chain and the reservoir is proportional to the
difference between the temperatures of the two systems, which is Newton’s
classical law of heating.

##  4 Conclusion

To sum up, we have derived the heat transport equation in dielectrics and
semiconductors starting from a Markovian master equation for the one-
dimensional lattice. We first derived the equations of motion for the discrete
lattice and discussed the contribution of the energy currents at the
microscopic level. We found that the range over which these currents influence
energy transport extends beyond the lattice constant, a fact that depends on
both the phonons decay time and the speed of propagation. The effect of the
environment is shown to be equivalent to a source density that depends on the
diffusion coefficients and implicitly on the decay time. We evaluated the rate
of change of the energy density in the continuum limit and showed that in this
limit, which is associated with long wavelength phonons, the speed of
propagation of heat is constant, which turns out to be the speed of
propagation of sound in the lattice. The thermal conductivity takes a form
similar to that of gases, and depends on the temperature through the heat
capacity density of the lattice. At high temperatures, the latter is constant,
and by calculating the exact form of the diffusion coefficients, we recover
the classical heat equation.

It is quite interesting to extend the investigation to the case of strong
coupling between the lattice and the environment, where quantum fluctuations
play an important role. In this regime, the dynamics is most likely to be non-
Markovian at low temperatures, and the exact treatment of the non-Markovian
dynamics is still an open problem that is not fully solved even for systems
with few degrees of freedom. One can invoke for example the path integral
technique which is cumbersome even for one oscillator. One of the main
features of the non-Markovian dynamics is the time dependence of the damping
coefficients and eventually of the diffusion coefficients. The energy currents
in this case may display very complicated behavior due to memory effects which
certainly affects the thermal conductivity. However, at high temperatures,
under the assumption that memory effects and quantum fluctuations become
negligible, one expects that the dynamics reproduces the classical thermal
transport equations as is the case for weak coupling which is the main aim of
this work.

## Appendix

For nonzero values of the damping coefficient $\gamma$, the diffusion
coefficients at arbitrary temperature read:

$\displaystyle D_{xx}$ $\displaystyle=$ $\displaystyle\frac{\hbar}{4\pi
m}\int_{-\pi}^{\pi}\frac{\coth\left(\frac{\hbar\omega(q)}{2k_{B}T_{f}}\right)}{\omega(q)}[\lambda+2\gamma\cos(q)]dq,$
(62) $\displaystyle D_{pp}$ $\displaystyle=$ $\displaystyle\frac{\hbar
m}{4\pi}\int_{-\pi}^{\pi}\coth\left(\frac{\hbar\omega(q)}{2k_{B}T_{f}}\right)\omega(q)[\lambda+2\gamma\cos(q)]dq,$
(63) $\displaystyle D_{\rm{ex}}$ $\displaystyle=$
$\displaystyle\frac{\hbar}{4\pi
m}\int_{-\pi}^{\pi}\frac{\coth\left(\frac{\hbar\omega(q)}{2k_{B}T_{f}}\right)}{\omega(q)}\cos(q)[\lambda+2\gamma\cos(q)]dq.$
(64)

In the limit of high temperature, we find:

$\displaystyle D_{xx}$ $\displaystyle=$ $\displaystyle\frac{\lambda
k_{B}T_{f}}{m\omega_{0}\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}+\frac{\gamma
k_{B}T_{f}}{\xi\omega_{0}}\left(\frac{\omega_{0}^{2}+\frac{2\xi}{m}-\omega_{0}\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}{\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}\right),$
(65) $\displaystyle D_{pp}$ $\displaystyle=$ $\displaystyle m\lambda
k_{B}T_{f},$ (66) $\displaystyle D_{\rm{ex}}$ $\displaystyle=$
$\displaystyle\frac{\lambda
k_{B}T_{f}}{\xi\omega_{0}}\left(\frac{\omega_{0}^{2}+\frac{2\xi}{m}-\omega_{0}\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}{\sqrt{\omega_{0}^{2}+\frac{4\xi}{m}}}\right)$
(67) $\displaystyle+$ $\displaystyle\frac{(2\gamma
k_{B}T_{f})/(m\omega_{0}^{2})}{1+\frac{2\xi}{2\xi+m\omega_{0}^{2}}+\sqrt{1+\frac{4\xi}{m\omega_{0}^{2}}}}.$

By direct substitution into equation (32) we find once again that:

$s(T_{f})=\frac{2\lambda k_{B}T_{f}}{a}.$ (68)

## References

## References

  * [1] Kittel C 1953 Introduction to Solid State Physics (New York: Wiley).
  * [2] Ziman J M 1999 Principles of the Theory of Solids (Cambridge: Cambridge Univ. Press).
  * [3] Ziman J M 2001 Electrons and Phonons: The Theory of Transport Phenomena in Solids (New York: Oxford University Press).
  * [4] Klemens P G 1958 Thermal Conductivity and Lattice Vibrational Modes, in Solid State Physics, Vol. 7 (Elsevier), pp. 1–98.
  * [5] Wu L -A and Segal D 2008 Phys. Rev. E 77 060101 .
  * [6] Dubi Y and Di Ventra M 2009 Phys. Rev. E 79 042101 .
  * [7] Li J -X, Liu F and Chen T 2010 Mod. Phys. Lett. B 24 521\.
  * [8] Dhar A and Sriram Shastry B 2003 Phys. Rev. B 67 195405\.
  * [9] Mendoza-Arenas J J, Al-Assam S, Clark S R and Jaksch D 2013 J. Stat. Mech. 2013 P07007.
  * [10] Asadian A, Manzano D, Tiersch M and Briegel H J 2013 Phys. Rev. E 87, 012109.
  * [11] Motz T, Wiedmann M, Stockburger J T and Ankerhold J 2018 New J. Phys. 20, 113020.
  * [12] Oliveira D, Pereira E and Lemos H C F 2020 J. Phys. A: Math. Theor. 53, 375007 .
  * [13] Novakovic B and Knezevic I 2011 Quantum Master Equations in Electronic Transport, in Nano-Electronic Devices: Semiclassical and Quantum Transport Modeling, edited by D. Vasileska and S. M. Goodnick ( New York: Springer) pp. 249–287.
  * [14] Yan Y, Wu C -Q, Casati G, Prosen T, and Li B 2008 Phys. Rev. B 77, 172411.
  * [15] Zhou H, Thingna J, Wang J -S, and Li B 2015 Phys. Rev. B 91, 045410.
  * [16] Hofer P P, Perarnau-Llobet M, Miranda L D M, Haack G, Silva R, Brask J B and Brunner N 2017 New J. Phys. 19, 123037.
  * [17] Pekola J P and Karimi B 2021 Rev. Mod. Phys. 93, 041001.
  * [18] Quan H T, Liu Y, Sun C. P. and Nori F 2007 Phys. Rev. E 76, 031105.
  * [19] Abah O, Roßnagel J, Jacob G, Deffner S, Schmidt-Kaler F, Singer K and Lutz E 2012 Phys. Rev. Lett. 109, 203006.
  * [20] Hofer P P and Sothmann B 2015 Phys. Rev. B 91, 195406.
  * [21] Leggio B, Bellomo B and Antezza M 2015 Phys. Rev. A 91, 012117.
  * [22] Hardal A Ü C, Aslan N, Wilson C M and Müstecaplıoğlu Ö E 2017 Phys. Rev. E 96, 062120.
  * [23] Hofer P P, Brask J B, Perarnau-Llobet M and Brunner N 2017 Phys. Rev. Lett. 119, 090603.
  * [24] Binder F, Correa L A, Gogolin C, Anders J, and Adesso G (eds) 2018 Thermodynamics in the Quantum Regime: Fundamental Aspects and New Directions (Berlin: Springer).
  * [25] D’Alessandro D 2008 Introduction to Quantum Control and Dynamics (Boca Raton: Chapman & Hall/CRC).
  * [26] Breuer H P and Petruccione F 2002 _The Theory of Open Quantum Systems_ ( Oxford: Oxford University Press).
  * [27] Weiss U 1993 Quantum Dissipative Systems (Singapore: World Scientific).
  * [28] Hamdouni Y 2010 J. Phys. G: Nucl. Part. Phys. 37, 125106.
  * [29] Hamdouni Y and Benrachi F 2013 J. Phys. A: Math. Theor. 46, 355303.
  * [30] Lindblad G 1976 Commun. Math. Phy. 48, 119.
  * [31] Lindblad G 1976 Rep. Math. Phys. 10, 393.