14

# Efficient Algorithms and Hardness Results
for the Weighted $k$-Server Problem

Anupam Gupta Computer Science Department, Carnegie Mellon University,
Pittsburgh, PA. Email<EMAIL_ADDRESS>Supported in part by NSF awards
CCF-1955785, CCF-2006953, and CCF-2224718. Amit Kumar Department of Computer
Science and Engineering, IIT Delhi, New Delhi, India. Email:
<EMAIL_ADDRESS>Debmalya Panigrahi Department of Computer Science, Duke
University, Durham, NC. Email<EMAIL_ADDRESS>Supported in part by NSF
awards CCF-1750140 (CAREER) and CCF-1955703.

###### Abstract

In this paper, we study the weighted $k$-server problem on the uniform metric
in both the offline and online settings. We start with the offline setting. In
contrast to the (unweighted) $k$-server problem which has a polynomial-time
solution using min-cost flows, there are strong computational lower bounds for
the weighted $k$-server problem, even on the uniform metric. Specifically, we
show that assuming the unique games conjecture, there are no polynomial-time
algorithms with a sub-polynomial approximation factor, even if we use
$c$-resource augmentation for $c<2$. Furthermore, if we consider the natural
LP relaxation of the problem, then obtaining a bounded integrality gap
requires us to use at least $\ell$ resource augmentation, where $\ell$ is the
number of distinct server weights. We complement these results by obtaining a
constant-approximation algorithm via LP rounding, with a resource augmentation
of $(2+\varepsilon)\ell$ for any constant $\varepsilon>0$.

In the online setting, an $\exp(k)$ lower bound is known for the competitive
ratio of any randomized algorithm for the weighted $k$-server problem on the
uniform metric. In contrast, we show that $2\ell$-resource augmentation can
bring the competitive ratio down by an exponential factor to only
$O(\ell^{2}\log\ell)$. Our online algorithm uses the two-stage approach of
first obtaining a fractional solution using the online primal-dual framework,
and then rounding it online.

##  1 Introduction

The $k$-Server problem is a foundational problem in online algorithms and has
been extensively studied over the last 30 years [BEY98]. In this problem,
there are a set of $k$ servers that must serve requests arriving online at the
vertices of an $n$-point metric space. The goal is to minimize the total
movement cost of the servers. The $k$-Server problem was defined by Manasse et
al. [MMS90], who also showed a lower bound of $k$ on the competitive ratio of
any deterministic algorithm for this problem. Koutsoupias and Papadimitriou
[KP95b] gave a $(2k-1)$-compeititive algorithm for $k$-Server. There has been
much progress in the recent past on obtaining randomized algorithms with
polylogarithmic (in $k$ and $n$) competitive ratio [BBMN15, BCL+18, Lee18,
BGMN19]. The Weighted $k$-Server version of this problem, introduced by Fiat
and Ricklin [FR94], allows the servers to have non-uniform positive weights;
the cost of moving a server is now scaled by its weight. In this paper, we
consider the Weighted $k$-Server problem on a uniform metric, namely when all
$n$ points of the metric space are at unit distance from each other, which
means that the cost of moving a server between any two distinct points is
simply the weight of the server. Note that the corresponding unweighted
problem for the uniform metric is the extensively studied Paging problem
[BEY98]. Indeed, one of the original motivations for studying the Weighted
$k$-Server problem came from a version of paging with non-uniform replacement
costs for different cache slots [FR94]. In the rest of this paper, we will
implicitly assume that the underlying metric space is a uniform metric.

The original paper of Fiat and Ricklin [FR94] introducing the Weighted
$k$-Server problem (on uniform metrics) gave a deterministic algorithm with a
competitive ratio of about $2^{2^{2k}}$. They also showed a lower bound of
$(k+1)!/2$ for deterministic algorithms. Chiplunkar and Viswanathan [CV20]
improved this lower bound to $(k+1)!-1$, and gave a randomized algorithm that
is $1.6^{2^{k}}$-competitive against _adaptive_ online adversaries; this also
implies a deterministic competitive ratio of $2^{2^{k+1}}$ using the
simulation technique of Ben-David et al. [BDBK+94]. Bansal, Elias, and
Koumutsos [BEK17] showed that this competitive ratio is essentially tight for
deterministic algorithms by showing a lower bound of $2^{2^{k-4}}$. They also
gave a deterministic work function algorithm with a competitive ratio of
$2^{2^{k+O(\log k)}}$. If the number of distinct server weights is $\ell$ and
there are $k_{j}$ servers of weight $W_{j}$, then the competitive ratio of
their algorithm is $\exp(O(\ell k^{3}\prod_{j=1}^{\ell}(k_{j}+1)))$, which is
an exponential improvement over the general bound when $\ell$ is a constant.
Unlike the $k$-Server and Paging problems, it is unknown if randomization
qualitatively improves the competitive ratio for Weighted $k$-Server, although
the best known lower bound for randomized algorithms against oblivious
adversaries is only singly exponential in $k$ [AC21] as against the doubly
exponential lower bound for deterministic algorithms.

The above competitive ratios depend only on $k$, and are independent of the
size $n$ of metric space. Moreover, the hard instances are for metric spaces
with the number of points $n$ that are exponentially larger than the number of
servers $k$. This is not a coincidence, since better algorithms exist for
smaller values of $n$. Indeed, the Weighted $k$-Server problem can be modeled
as a metrical task system, where each state $\omega$ is a configuration
(specifying the location of each of the $k$ servers), and the distance between
any two states $\omega,\omega^{\prime}$ is the cost to move between the
configurations. Since there are $N=n^{k}$ states, one can obtain an
$n^{k}$-competitive deterministic algorithm [BLS92], and an
$O(\operatorname{poly}(k\log n))$-competitive randomized algorithm against
_oblivious_ adversaries [BBBT99, BBN10, BCLL21, CL22]; all these algorithms
use $\operatorname{poly}(n^{k})$ time to explicitly maintain and manipulate
the entire metric space, and hence are not efficient.

In this paper we ask: _is it possible to get efficient (randomized)_online_
algorithms that have competitive ratios of the form $\operatorname{poly}(k\log
n)$, or even better? Is it possible to get such approximation ratios even in
the _offline_ setting?_ We show that obtaining improved competitive or
approximation ratios in polynomial time is possible, provided we allow for
resource augmentation in the number of servers.

Resource augmentation in online algorithms has been widely studied in paging
and scheduling settings (see e.g. [KP95a, ST85]). It is often a much needed
assumption that allows for obtaining bounded or improved competitive ratios
for such problems. Bansal et al. [BEJK19] studied the $k$-Server problem on
trees under resource augmentation.

###  1.1 Our Results

Our first result establishes computational hardness of approximating the
Weighted $k$-Server problem in the offline setting. Unlike Paging or
$k$-Server, which are exactly solvable offline in polynomial time, we show
that under the Unique Games conjecture, the Weighted $k$-Server problem cannot
be approximated to any subpolynomial factor even when we allow $c$-resource
augmentation for any constant $c<2$.

######  Theorem 1.1 (Hardness).

For any constant $\varepsilon>0$, it is UG-hard to obtain an
$N^{\nicefrac{{1}}{{2}}-\varepsilon}$-approximation algorithm for Weighted
$k$-Server with two weight classes, even when we are allowed $c$-resource
augmentation for any constant $c<2$. Here $N$ represents the size of the input
(including the request sequence length).

Next, we show that the natural time indexed LP relaxation for Weighted
$k$-Server (see LP) has a large integrality gap, unless we allow for a
resource augmentation of almost $\ell$, the number of distinct server weights.

######  Theorem 1.2 (Integrality Gap).

For any constant $\varepsilon>0$, the integrality gap of the relaxation LP for
Weighted $k$-Server is unbounded, even with $(\ell-\varepsilon)$-resource
augmentation.

It is worth noting that an optimal fractional solution to LP can be easily
rounded to give an $\ell$-approximation ratio with $\ell$-resource
augmentation. Indeed, we know that for each request, there exists a weight
class which services this request to an extent of at least
$\nicefrac{{1}}{{\ell}}$. We can then scale this fractional solution by a
factor $\ell$ and reduce this problem to $\ell$ instances of standard Paging
problem. The integrality gap result shows that any rounding algorithm with
bounded competitive ratio must incur almost $\ell$-resource augmentation. We
complement this integrality gap result with our main technical result, which
gives an offline $O(1/\varepsilon)$-approximation with
$(2+\varepsilon)\ell$-resource augmentation, for any $\varepsilon\in(0,1)$.

######  Theorem 1.3 (Offline Algorithm).

Let ${\mathcal{I}}$ be an instance of Weighted $k$-Server with $k_{j}$ servers
of weight $W_{j}$ for all $j\in[\ell]$. For any $\varepsilon\in(0,1)$, there
is a polynomial time algorithm for ${\mathcal{I}}$ that uses at most
$2(1+\varepsilon)\ell\cdot k_{j}$ servers of weights $W_{j}$ for each
$j\in[\ell]$ and has server movement cost at most $O(1/\varepsilon)$ times the
optimal cost of ${\mathcal{I}}$.

Finally, we obtain an online algorithm for Weighted $k$-Server with
$2\ell$-resource augmentation. The competitive ratio of the online algorithm
is $O(\ell^{2}\log\ell)$. (In constrast to the offline setting, it is no
longer clear how to achieve an $\ell$-competitive algorithm even if we augment
the number of servers by a factor of $\ell$.)

######  Theorem 1.4 (Online Algorithm).

Let ${\mathcal{I}}$ be an instance of Weighted $k$-Server with $k_{j}$ servers
of weight $W_{j}$ for all $j\in[\ell]$. There is a randomized (polynomial
time) online algorithm for ${\mathcal{I}}$ that uses at most $2\ell k_{j}$
servers of weights $W_{j}$ for each $j\in[\ell]$ and has expected server
movement cost at most $O(\ell^{2}\log\ell)$ times the optimal cost of
${\mathcal{I}}$.

Since $\ell\leq k$, the competitive ratio of the online algorithm is
$O(k^{2}\log k)$. This implies that an $O(\ell^{2})$-resource augmentation
achieves at least an exponential improvement in the competitive ratio of the
Weighted $k$-Server problem. Moreover, by rounding the weights to powers of
$2$, we can assume that $\ell\leq O(\log W)$, where $W$ is the aspect ratio of
the server weights. Hence, the competitive ratio of the online algorithm is
$O(\log^{2}W\log\log W)$. Finally, note that for $\ell=O(1)$, the above
theorem gives a $O(1)$-competitive online algorithm with $O(1)$-resource
augmentation. This can be seen as a generalization of the classic result for
the Paging problem that achieves a randomized competitive ratio of
$O(\log\frac{k}{k-h+1})$ where the algorithm’s cache has $k$ slots while the
adversary’s has only $h<k$ slots [You91].

###  1.2 Our Techniques

In this section, we give an overview of the main techniques in the paper. The
UG hardness of Weighted $k$-Server is based on a reduction from the Vertex
Cover problem. Given an instance of the vertex cover problem, the
corresponding Weighted $k$-Server consists of one point in the uniform metric
space for each vertex of the graph. The main observation is that if we know
the minimum vertex cover size, we can keep one heavy weight server at each
point corresponding to this vertex cover, which never change their positions.
One can then generate an input sequence where the optimal solution pays a
small cost, whereas an algorithm which does not cover an edge using heavy
servers pays a much higher cost. The UG-hardness result for Vertex Cover
translates to a corresponding resource augmentation lower bound for Weighted
$k$-Server. Extending this approach to more than two weight classes (with
stronger lower bounds on resource augmentation) turns out to be more
challenging because the length of the input sequence becomes exponential in
$n$. Instead, we show that the natural LP relaxation has a large integrality
gap. The large gap instance consists of cycling through a sequence of subsets
of the metric spaces with carefully varying frequency. The fractional solution
is able to maintain a low cost by uniformly spreading servers over such
cycles, but the integral solution is forced to service some of the cycles by
small number of servers only.

Our main technical result shows how to round a solution to the LP relaxation.
The relaxation has both covering and packing type constraints, and the
rounding carefully addresses one set of constraints without violating the
other. We first scale the LP by a factor of about $2\ell$, thus increasing
both the resource augmentation and the cost. As a result, each request
$\sigma_{t}$ is covered to an extent of $2\ell,$ and we can split this
coverage across those weight classes which cover $\sigma_{t}$ to an extent of
at least 1. Now for a fixed weight class, we consider the requests which are
covered by it to an extent of at least 1. We show how to integrally round this
solution so that this coverage property is satisfied and yet, we do not
violate any packing constraint. After this, we show that the packing
constraints can be ignored. This allows to scale down the LP solution by a
factor $\ell$ (which saves the cost by this factor) and uses total
unimodularity of the constraint matrix to round it.

We extend our approximation algorithm to the online setting. The first step is
to maintain an online fractional solution to the LP relaxation. Standard
(weighted) paging algorithms for this problem rely on the fact that even the
optimal offline algorithm needs to place a server at a requested location. But
this turns out to be trickier here as we do not know the weight of the server
which serves this location in the optimal solution. So we serve a request by
ensuring that fractional mass from each weight classes is transferred at the
same rate. The overall analysis proceeds by a careful accounting in the
potential function. The online fractional solution satisfies the stronger
guarantee that each request is served by servers of a particular weight class
only. This allows us to reduce the rounding problem to independent instances
of the Paging problem.

We now give an overview of the rest of the submission. In §3, we give details
of the integrality gap construction; we defer the UG hardness proof to §2. The
offline rounding of the LP relaxation is given in §4, and then we extend this
algorithm to the online case in §5.

###  1.3 Preliminaries

In the Weighted $k$-Server problem on the uniform metric, we are given a set
of $n$ points $V=\\{1,\ldots,n\\}$, such that $d(v,v^{\prime})=1$ for each
$v\neq v^{\prime}$. There are $k$ servers, labeled $1,\ldots,k$, with server
$i$ having weight $w_{i}\geq 0$. The input specifies a request sequence
$(\sigma_{1},\ldots,\sigma_{T})$ of length $T$, with each request $\sigma_{t}$
arriving at time $t$ being a point in $V$. A solution
$f:[k]\times\\{0,\ldots,T\\}\to V$ specifies the position of each server at
each time $t\in[T]$ (where the initial positions $f(i,0)$ are specified as
part of the problem statement) such that for each time $t$ there exists some
server $i_{t}$ such that $f(i_{t},t)=\sigma_{t}$. The cost of the solution $f$
is the total weighted distance travelled by the servers, i.e.,

$\nicefrac{{1}}{{2}}\sum_{i=1}^{k}w_{i}\;\sum_{t=1}^{T}\mathbbm{1}[f(i,t)\neq
f(i,t-1)].$

The goal is to find a solution with the minimum cost. We say that an instance
has $\ell$ weight classes if the set $\\{w_{1},\ldots,w_{k}\\}$ has
cardinality $\ell$. For an instance with $\ell$ different weight classes, we
denote the distinct weights by $W_{1},\ldots,W_{\ell}$, and let $k_{j}$ denote
the number of servers of weight $W_{j}$, with $\sum_{j}k_{j}=k$. For such an
instance and a parameter $c\geq 1$, we say that the algorithm uses _$c$
-resource augmentation_ if it uses $\lfloor ck_{j}\rfloor$ servers of weight
$W_{j}$ for each $j=1,\ldots,\ell$.

We now describe the natural LP relaxation for Weighted $k$-Server. It has a
variable $x(v,j,t)$ for each request time $t$, weight class $j\in[\ell]$ and
vertex $v\in V$; it denotes the fractional mass of servers of weight $W_{j}$
that are present at point $v$ at time $t$. Let $\sigma_{t}$ denote the vertex
requested at time $t$. It is easy to verify that this is a valid relaxation.

$\displaystyle\min\nicefrac{{1}}{{2}}\sum_{j\in[\ell]}W_{j}\sum_{t}\sum_{v\in
V}$ $\displaystyle\;|x_{v,j,t}-x_{v,j,t-1}|$ (LP) $\displaystyle\sum_{v\in
V}x_{v,j,t}$ $\displaystyle\leq k_{j}$ $\displaystyle\forall t,j\in[\ell]$ (1)
$\displaystyle\sum_{j\in[\ell]}x_{\sigma_{t},j,t}$ $\displaystyle\geq 1$
$\displaystyle\forall t$ (2) $\displaystyle x_{v,j,t}$ $\displaystyle\geq 0$
$\displaystyle\forall t,v\in V,j\in[\ell]$

##  2 The Unique Games Hardness

In this section, we consider the special case of Weighted $k$-Server when
there are only two weight classes. Assume wlog that the two distinct weights
are 1 and $W$, where $W\gg 1.$ Our first main result shows that getting a good
approximation algorithm with $(2-\varepsilon)$-resource augmentation for any
constant $\varepsilon>0$ is as hard as getting a better-than-two approximation
for the vertex cover problem.

See 1.1

###### Proof.

We give a reduction from the Vertex Cover problem. Let $d=d(\varepsilon)$ be a
constant to be fixed later, and let $c<2$ be a constant as in the statement of
the theorem. Let ${\mathcal{I}}=(G=(V,E),t)$ be an instance of the Vertex
Cover problem on $n$ vertices. We know that it is UG-hard to distinguish
between the following two cases: (i) $G$ has a vertex cover of size at most
$t$, or (ii) every vertex cover of $G$ must have size strictly larger than
$ct$.

We map ${\mathcal{I}}$ to an instance ${\mathcal{I}}^{\prime}$ of Weighted
$k$-Server as follows: the set of points in ${\mathcal{I}}^{\prime}$ is given
by $V\cup\\{v_{0}\\}$, where $v_{0}$ is a special vertex. There are $t$
servers of weight $W=n^{d}$ and one server of unit weight. Let the edges in
$E$ be $e_{1},\ldots,e_{m}$. A subsequence of the request sequence consists of
$m$ phases, where we have a phase for each edge $e_{i}$. During phase $i$
corresponding to edge $e_{i}=(u_{i},v_{i})$, the request sequence toggles
between $u_{i}$ and $v_{i}$ for $W$ times. Finally, the subsequence is
repeated $W$ times. In other words, it is the following sequence

$\big{(}\underbrace{u_{1},v_{1},u_{1},v_{1},\ldots,u_{1},v_{1}}_{W\
\mbox{times}},\ldots,\underbrace{u_{m},v_{m},u_{m},v_{m},\ldots,u_{m},v_{m}}_{W\
\mbox{times}}\big{)}^{W}.$

We also have to specify the initial location of the servers. Assume that all
servers are at location $v_{0}$ in the beginning. This completes the
description of the instance ${\mathcal{I}}^{\prime}$. Observe that $N$, the
number of requests in instance ${\mathcal{I}}^{\prime}$ is $O(m\cdot n^{2d})$.

######  Claim 2.1.

Suppose $G$ has a vertex cover of size at most $t$. Then the cost of the
optimal solution for ${\mathcal{I}}^{\prime}$ is at most $2mW$.

###### Proof.

Let $V^{\prime}\subseteq V$ be a vertex cover of size $t$. Consider the
following solution: we move the $t$ heavy servers from $v_{0}$ to $V^{\prime}$
at the beginning. From now on, the heavy servers will not move at all. During
a phase corresponding to an edge $e_{i}=(u_{i},v_{i})$, we know that at least
one of these vertices will be occupied by a heavy server. If the other end-
point, say $v_{i}$, is not occupied by a heavy server, we move the server of
weight 1 to $v_{i}$. Now we have two servers occupying $u_{i}$ and $v_{i}$
respectively until the end of this phase. The total movement cost is incurred
either at the beginning (which is $tW$ overall), or at the beginning of each
phase (when the cost is 1). Since there are $mW$ phases, the overall cost is
at most $tW+mW\leq 2mW$. ∎

######  Claim 2.2.

Suppose every vertex cover in $G$ has size strictly larger than $ct$. Then
cost of the optimal solution for ${\mathcal{I}}^{\prime}$, even with
$c$-resource augmentation, is at least $W^{2}$.

###### Proof.

Consider any solution for ${\mathcal{I}}^{\prime}$. Recall that the input
consists of $W$ subsequences, call these $S_{1},\ldots,S_{W}$, where each
subsequence $S_{j}$ consists of $m$ phases, one for each edge of $G$. We claim
that during each such subsequence $S_{j}$, the solution must pay movement cost
of at least $W$. Indeed, consider a subsequence $S_{j}$. If the solution moves
a heavy server during $S_{j}$, then the claim follows directly. Else observe
that the size of any vertex cover is strictly larger than the number of heavy
servers $ct$, so there is some edge $e_{i}=(u_{i},v_{i})$ not covered by the
heavy servers during $S_{j}$. Now the phase for $e_{i}$ in $S_{j}$ would
require the unit weight server to toggle between $u_{i}$ and $v_{i}$ for $W$
times. In either case, the cost of each subsequence is at least $W$, and the
overall cost of the solution is at least $W^{2}$. ∎

The above two results along with the UG-hardness result for Vertex Cover
impliy that it is UG-hard to obtain a $\frac{W^{2}}{2mW}$-approximation for
Weighted $k$-Server with two weight classes. This ratio is equal to
$\frac{W}{2m}\geq n^{d-2}\geq N^{\nicefrac{{1}}{{2}}-\varepsilon}$, assuming
$d$ is $\Omega(\nicefrac{{1}}{{\varepsilon}})$, which proves Theorem 1.1. ∎

##  3 An Integrality Gap for the Natural Linear Program

In this section, we show that the relaxation LP for Weighted $k$-Server has a
large integrality gap, unless we allow for a resource augmentation of almost
$\ell$, the number of distinct server weights.

Recall that the $\ell$ weights are denoted $W_{1}\gg\cdots\gg W_{\ell}$, and
there are $k_{j}$ servers of weight $W_{j}$. Our theorem is the following:

See 1.2

An Instance for Two Classes. To gain some intuition, we first consider the
special case of $\ell=2$, and prove the result without giving any resource
augmentation. There are $\nicefrac{{n}}{{2}}$ servers of weight $W$ and
$\nicefrac{{n}}{{4}}$ servers of weight $1$, thereby giving a total of
$k=\nicefrac{{3n}}{{4}}$ servers. The input is given in “phases”. Each phase
is specified by a distinct subset $S$ of $V$, where $|S|=\nicefrac{{n}}{{2}}$.
During the phase corresponding to a subset $S$, we cycle through all subsets
$S^{\prime}$ of $S$ with
$|S^{\prime}|=\nicefrac{{|S|}}{{2}}=\nicefrac{{n}}{{4}}$. Given such a subset
$S^{\prime}$ of $S$, we send requests which cycle through the points in
$S^{\prime}$ for $L$ times, where $L$ is large enough.

One fractional solution for such a sequence is defined as follows: we assign
$\nicefrac{{1}}{{2}}$ unit of weight-$W$ server at each of the $n$ locations.
During the phase for a subset $S$, we assign $\nicefrac{{1}}{{2}}$ unit of
server of unit weight at each of the locations in $S$. The cost of the
fractional solution is at most $Z:={n\choose n/2}\cdot\nicefrac{{n}}{{4}}$
(not accounting for the initial movement of the servers). However, an integral
solution either moves at least one heavy server, or else pays at least $L$
during one of the phases, thereby must pay at least $\min(W,L)$. Assuming
$W,L\gg Z$ gives an arbitrarily large integrality gap. (We can account for the
initial movement of the fractional servers by repeating the process some $M$
times: the integral solution would pay at least $\min(W,L)$ in each such
iteration and the fractional solution would pay at most $Z$, so that the
initial movement cost would get amortized away.)

The Instance for $\ell$ Classes. We extend this construction to larger values
of $\ell$ by defining phases in a recursive manner on a nested sequence of
subsets of $V$, with each phase containing several repetitions of the same
sequence. Instead of decreasing by a factor 2, the number of servers of each
weight class now goes down by a factor of $C\geq\ell$. This allows the
integrality gap result to hold even when the integral solution is allowed a
resource augmentation of nearly $\ell$.

For some $r\leq\ell-1$, we call a tuple $(S_{0},\ldots,S_{r})$ _valid_ if (i)
$S_{0}=V$ and each $S_{j}\subseteq S_{j-1}$, and (ii)
$|S_{j}|=|S_{j-1}|/C=\nicefrac{{n}}{{C^{j}}}$. The request sequence is
generated by calling Algorithm 1 with the trivial valid sequence $(S_{0}=V)$.
Given a valid tuple $(S_{0},\ldots,S_{r})$, the procedure cycles through all
subsets $S\subseteq S_{r}$ of size $|S_{r}|/C$ and recursively calls
${\mathsf{Generate}}(S_{0},\ldots,S_{r},S)$; this process is repeated $L_{r}$
times. Finally, in the base case when $r=\ell-1$, it cycles through all the
locations in $S_{\ell}$ for $L_{\ell-1}$ times. For a suitably large choice of
$M$, we define for each $r\in[\ell]$:

$\displaystyle L_{r}:=M^{r}\qquad\text{and}\qquad W_{r}:=M^{\ell-r}.$ (3)

Finally, the number of servers of weight $W_{r}$ is given by
$k_{r}:=\frac{n}{\ell C^{r-1}}$.

0.1 Input: A valid tuple $(S_{0},S_{1},\ldots,S_{r})$ ;

0.2 repeat

0.3 if  _$r$ is equal to $\ell-1$_ then

0.4 Send a request at each location in $S_{\ell-1}$. ;

0.5 else

0.6 for  _each subset $S$ of $S_{r}$ with $|S|=\frac{|S_{r}|}{C}$_ do

0.7 // Move $\nicefrac{{1}}{{\ell}}$ mass of servers of weight $W_{r+2}$ to
$S$ ;

0.8 Call ${\mathsf{Generate}}(S_{0},\ldots,S_{r},S)$. ;

0.9

0.10

0.11

0.12until  _$L_{r}$ iterations have occurred_;

Algorithm 1 Procedure ${\mathsf{Generate}}(S_{0},S_{1},\ldots,S_{r})$.

###  3.1 Analyzing the Integrality Gap

We bound the cost of the optimal fractional solution for the above input
sequence.

######  Lemma 3.1.

There is a fractional solution of total cost $O(f(n)M^{\ell-2})$ for the input
sequence constructed by Algorithm 1, where $f(n)$ is a function solely of $n$.

###### Proof.

Our fractional solution maintains the invariant: when the procedure
${\mathsf{Generate}}(S_{0},\ldots,S_{r})$ is called, we have
$\nicefrac{{1}}{{\ell}}$ fractional mass of servers of weight
$W_{1},\ldots,W_{r+1}$ respectively at each location in $S_{r}$. For the base
case $r=0$, we place $\nicefrac{{1}}{{\ell}}$ server mass at each location in
$S_{0}=V$; recall that $k_{1}=\nicefrac{{n}}{{\ell}}$. For the inductive step,
suppose this invariant is satisfied for a certain value of $r$ where $0\leq
r<\ell-1$; we need to show that it is satisfied for $r+1$ as well. Indeed, the
induction hypothesis implies that we have $\nicefrac{{1}}{{\ell}}$ amount of
server mass of weight $W_{1},\ldots,W_{r+1}$ at each location in $S_{r}$, and
hence at each location in $S_{r+1}$. Moreover, as line 1 indicates, we move
$\nicefrac{{1}}{{\ell}}$ fractional mass of servers of weight $W_{r+2}$ to
each location in $S_{r+1}$ to satisfy the invariant condition. This costs
$W_{r+2}\,k_{r+2}/\ell$; moreover, this is feasible because the total number
of servers of weight $W_{r+2}$ needed is $\frac{|S_{r+1}|}{\ell}=\frac{n}{\ell
C^{r+1}}=k_{r+2}$. Finally, when $r=\ell-1$, the invariant shows that $1$ unit
of server mass is present at each of the locations in $S_{\ell}$, and hence
the requests generated in line 1 can be served without any additional movement
of servers.

We now account for the movement cost. The total server movement cost during
${\mathsf{Generate}}(S_{0},\ldots,S_{r})$ (not counting the movement costs in
the recursive calls) is at most
$O(L_{r}\,k_{r+1}\,W_{r+2})=O(k_{r+1}\,M^{\ell-2})$. Since $k_{r+1}\leq n$ and
the number of calls to ${\mathsf{Generate}}$ is a function only of $n$, the
overall movement cost can be expressed as $O(f(n)\cdot M^{\ell-2})$. (Again,
by repeating the entire process multiple times we can amortize away the
initial movement cost; we avoid this step for the sake of clarity.) ∎

The next lemma shows that any integral solution must have much higher cost.

######  Lemma 3.2.

Let $\varepsilon>0$ be a small enough constant. Assume that the integral
solution is allowed $(\ell-\varepsilon)k_{r}$ servers of weight $W_{r}$ for
each $r\in[\ell]$. Any integral solution for the input sequence generated by
Algorithm 1 (with $C=\nicefrac{{\ell}}{{\varepsilon}}$) has movement cost at
least $M^{\ell-1}.$

###### Proof.

We prove the following more general statement by reverse induction on $r$: any
integral solution for the sequence generated by
${\mathsf{Generate}}(S_{0},\ldots,S_{r})$ for a valid tuple
$(S_{0},\ldots,S_{r})$ which does not use any server of weight class
$W_{1},\ldots,W_{r}$ (at any location in $S_{r}$) has cost at least
$M^{\ell-1}$. It suffices to prove this statement, because the case when $r=0$
implies the lemma.

Consider the base case when $r=\ell-1$. Consider the sequence generated by
such a procedure ${\mathsf{Generate}}(S_{0},\ldots,S_{r})$ such that no server
of weight $W_{1},\ldots,W_{\ell-1}$ is used for serving the requests at
$S_{\ell-1}$. Thus all requests generated by this procedure must be served by
servers of weight $W_{\ell}$. Now, $|S_{\ell-1}|=\frac{n}{C^{\ell-1}}$,
whereas the number of weight $W_{\ell}$ servers available to the algorithm is
$(\ell-\varepsilon)k_{\ell}<\frac{n}{C^{\ell-1}}.$ Therefore, during each
iteration of the repeat-until loop in lines 1–1 in Algorithm 1, at least one
server of weight $W_{\ell}$ must move. So the overall movement cost during
this input sub-sequence is at least $W_{\ell}\cdot L_{\ell-1}=M^{\ell-1}$.
This proves the base case.

The inductive case is proved in an analogous manner. Suppose the statement is
true for $r+1$, and now consider the sub-sequence generated by
$Gen(S_{0},\ldots,S_{r})$ for some valid tuple $(S_{0},\ldots,S_{r})$. Assume
that no server of weight $W_{1},\ldots,W_{r}$ is present at any node in
$S_{r}$ during this time. We claim that the algorithm must incur movement cost
of at least $W_{r+1}$ during each iteration of the repeat-until loop. Indeed,
fix such an iteration. Two cases arise: (a) The algorithm moves a server of
weight $W_{r+1}$ then the claim follows trivially, or (b) No server of weight
$W_{r+1}$ is moved during this period. Now observe that
$|S_{r}|=\frac{n}{C^{r}}$, and the number of weight $W_{r+1}$ servers
available to the algorithm is $(\ell-\varepsilon)k_{r+1}=|S_{r}|-\varepsilon
k_{r+1}=|S_{r}|\left(1-\frac{1}{C}\right).$ Thus, there is a subset $S_{r+1}$
of $S$ of size $\frac{|S_{r}|}{C}=\frac{n}{C^{r+1}}$ where no server of weight
$W_{r+1}$ appears during this input sub-sequence. Consider the recursive call
${\mathsf{Generate}}(S_{0},\ldots,S_{r},S_{r+1})$ in line 1. The induction
hypothesis implies that the movement cost during this recursive call is at
least $M^{\ell-1}\geq W_{r+1}$.

Thus, we have shown that the movement cost during each iteration of the
repeat-until loop during ${\mathsf{Generate}}(S_{0},\ldots,S_{r})$ is at least
$W_{r+1}$. Since there are $L_{r}$ such iterations, the overall movement cost
is at least $W_{r+1}\cdot L_{r}=M^{\ell-1}.$ This completes the proof of the
induction hypothesis, and implies the lemma. ∎

Combining Lemma 3.1 and Lemma 3.2 proves Theorem 1.2.

##  4 An Offline Algorithm via LP Rounding

We now show an algorithm for the offline setting, that rounds any fractional
solution to the LP relaxation (LP), and achieves the following guarantee: See
1.3

Instead of working with the relaxation (LP), we work with an equivalent
relaxation which turns out to be easier to interpret. For each vertex $v\in
V$, index $j\in[\ell]$ and time interval $I$, we have a variable $y_{v,j,I}$,
which denotes the fractional mass of server of weight $W_{j}$ residing at $v$
during the entire time interval $I$. The variable $x_{v,j,t}$ used in (LP) can
be expressed as follows:

$\displaystyle x_{v,j,t}=\sum_{I:t\in I}y_{v,j,I}.$ (4)

Let ${\mathbf{I}}$ denote the set of all intervals during the request
timeline. The new linear program relaxation for Weighted $k$-Server is the
following:

$\displaystyle\min\nicefrac{{1}}{{2}}\sum_{j\in[\ell]}W_{j}\;\sum_{I\in{\mathbf{I}}}\sum_{v\in
V}$ $\displaystyle y_{v,j,I}$ (LP2) $\displaystyle\text{s.t.
}\sum_{j\in[\ell]}\sum_{I:t\in I}y_{\sigma_{t},j,I}$ $\displaystyle\geq 1$
$\displaystyle\forall t$ (5) $\displaystyle\sum_{v\in V}\sum_{I:t\in
I}y_{v,j,I}$ $\displaystyle\leq k_{j}$ $\displaystyle\forall t,j\in[\ell]$ (6)
$\displaystyle y_{v,j,I}$ $\displaystyle\geq 0\qquad\qquad$
$\displaystyle\forall t,j\in[\ell],v\in V.$

Note that the covering constraint (5) enforces having at least one unit of
(fractional) server mass at the location $\sigma_{t}$ requested for each time
$t$. The packing constraint (6) enforces that the total (fractional) server
mass of weight $W_{j}$ used at any time $t$ is at most the number of servers
of this weight, namely $k_{j}$. Given a solution $y_{v,j,I}$ to LP2, the
variables $x_{v,j,t}$ defined using (4) define a feasible solution to LP of
the same cost.

Fix any constant $\varepsilon\in(0,1)$. We now prove Theorem 1.3 by rounding
an optimal fractional solution $y_{v,j,I}$ to LP2. The rounding algorithm has
two stages. The first stage scales and discretizes the LP variables to
integers such that

  1. nosep

the packing constraints are satisfied up to a factor of $(2+\varepsilon)\ell$,

  2. nosep

the covering constraints are satisfied with a scaled covering requirement of
$\ell$ instead of 1, i.e., $\sum_{j}\sum_{I:t\in
I}y_{\sigma_{t},j,I}\geq\ell,$ for all times $t$, and

  3. nosep

the cost of the fractional solution increases by a factor of
$O(\ell/\varepsilon)$.

In the second stage, we remove the packing constraints from the LP; this
results in the resulting interval covering LP being integral. Next, we scale
the solution from the first stage down by $\ell$, getting a feasible
fractional solution to the standard LP relaxation for the interval covering
problem. Finally, we use the integrality of the interval covering LP
relaxation to obtain an integral solution for LP2. We present these two stages
in the next two sections.

###  4.1 Stage I: Scaling and Discretization

0.1 Input: A fractional solution $(y_{v,j,I},x_{v,j,t})$ to LP2, a location
$v$ and a weight $W_{j}$;

0.2 Initialize variables ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ to
0 for all intervals $I$. ;

0.3 (Scale): Define
${\widetilde{y}}_{v,j,I}=\left(2+\nicefrac{{\varepsilon}}{{2}}\right)\ell\cdot
y_{v,j,I}$ and therefore, $\widetilde{x}_{v,j,t}=\sum_{I:t\in
I}{\widetilde{y}}_{v,j,I}=\left(2+\nicefrac{{\varepsilon}}{{2}}\right)\ell\cdot
x_{v,j,t}$ for each $I\in{\mathbf{I}}$. ;

0.4 (Round): for  _$h=1,2,\ldots,\ell$ _ do

0.5 Initialize ${\mathsf{LastEvent}}={\mathsf{DOWN}},{\mathsf{LastTime}}=0$. ;

0.6 repeat

0.7 if  _ ${\mathsf{LastEvent}}={\mathsf{UP}}$_ then

0.8 Let $t$ be the first ${\mathsf{DOWN}}$ after ${\mathsf{LastEvent}}$ ;

0.9 Update ${\mathsf{LastEvent}}={\mathsf{DOWN}},{\mathsf{LastTime}}=t.$

0.10 else

0.11 (${\mathsf{LastEvent}}={\mathsf{DOWN}}$) Let $t$ be the first
${\mathsf{UP}}$ after ${\mathsf{LastEvent}}$ ;

0.12 Add $I=[{\mathsf{LastTime}},t)$ to ${\mathbf{I}}_{v,j}(h)$ and increase
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ by 1. ;

0.13 Update ${\mathsf{LastEvent}}={\mathsf{DOWN}},{\mathsf{LastTime}}=t.$

0.14

0.15 until  _we have reached the end of the timeline $[0,T]$_;

Algorithm 2 Procedure ${\mathsf{ScaleRound}}(x,y,v,W_{j})$.

The first stage of the rounding algorithm operates independently on each
location $v\in V$ and for each server weight $W_{j}$; the formal algorithm
${\mathsf{ScaleRound}}(x,y,v,W_{j})$ is given in Algorithm 2. We work with
both the $y_{v,j,I}$ variables and the equivalent $x_{v,j,t}$ variables
defined in (4); this representational flexibility makes it convenient to
explain the algorithm. To begin, we scale the LP variables $y_{v,j,I}$ by a
factor $(2+\nicefrac{{\varepsilon}}{{2}})\ell$ to obtain
${\widetilde{y}}_{v,j,I}$ (we also define the auxiliary variables
$\widetilde{x}_{v,j,t}$ by scaling $x_{v,j,t}$ similarly).

_Discretization._ Next we discretize the scaled variables
${\widetilde{y}}_{v,j,I}$ and $\widetilde{x}_{v,j,t}$ to nonnegative integers
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ and
$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$ respectively. To start, let
us describe the discretization of $\widetilde{x}_{v,j,t}$ to obtain
$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$. Intuitively, we would like
to define $\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$ as
$\lfloor\widetilde{x}_{v,j,t}\rfloor$, i.e., the largest step function with
unit step sizes entirely contained in $\widetilde{x}_{v,j,t}$, but this can
amplify small fluctuations around integer values, and hence may increases the
cost. To avoid this, we introduce hysteresis in our discretization, by setting
different thresholds for increasing and decreasing the value of
$\widetilde{x}_{v,j,t}$. We view $\widetilde{x}_{v,j,t}$ as a time-varying
profile and define horizontal slabs in it corresponding to the restriction of
the range of $\widetilde{x}_{v,j,t}$ to $[h,h+1)$ for some integer $h$. For
each such slab, we identify intervals $I$ of width at most 1 and at least
$\nicefrac{{1}}{{2}}$ and set the increase the corresponding
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ value by 1. In more detail,
for each such level $h$, we identify a subset ${\mathbf{I}}_{v,j}(h)$ of
intervals for which the corresponding
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ variable is to be increased
by 1. We identify an alternating sequence of up and down events in the
timeline $[0,T]$ as follows:

  * •

${\mathsf{UP}}$ event: At time $t$, there is an ${\mathsf{UP}}$ event at level
$h$ if $\widetilde{x}_{v,j,t^{-}}<h$ and $\widetilde{x}_{v,j,t}\geq h$, and
the previous event at level $h$ was a ${\mathsf{DOWN}}$ event.

  * •

${\mathsf{DOWN}}$ event: At time $t$, there is a ${\mathsf{DOWN}}$ event at
level $h$ if the previous event at level $h$ was an ${\mathsf{UP}}$, and
$\widetilde{x}_{v,j,t^{-}}>h-\nicefrac{{\varepsilon}}{{2}}$ and
$\widetilde{x}_{v,j,t}\leq h-\nicefrac{{\varepsilon}}{{2}}$, or $t=T$, the end
of the timeline. (The reader should think of $\nicefrac{{\varepsilon}}{{2}}$
as the “hysteresis gap” between the up and down events at any level.)

To make the definition complete, we set $\widetilde{x}_{v,j,t}$ to 0 at
$t=0^{-}$ and at $t=T^{+}$, and start with a ${\mathsf{DOWN}}$ at time 0.
Finally, we add intervals stretching from each ${\mathsf{UP}}$ to the next
${\mathsf{DOWN}}$ to the set ${\mathbf{I}}_{v,j}(h)$ of intervals. By
construction, these intervals are mutually disjoint. Finally, whenever an
interval $I$ is added to such a set ${\mathbf{I}}_{v,j}(h)$, we increment the
corresponding variable ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$.
Thus we have:

${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}=|\\{h:I\in{\mathbf{I}}_{v,j}(h)\\}|,\text{
and correspondingly,
}\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}=\sum_{I:t\in
I}{\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}.$

The next lemma shows that $\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$ can
be thought of as a discretized form of $\widetilde{x}_{v,j,t}$:

######  Lemma 4.1.

The following holds for variables
$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$:

$\widetilde{x}_{v,j,t}-1<\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}<\widetilde{x}_{v,j,t}+\nicefrac{{\varepsilon}}{{2}}.$
(7)

###### Proof.

Suppose $\widetilde{x}_{v,j,t}\in[r,r+1)$. Consider the for loop in line 2 in
Algorithm 2 for a value $h\leq r$. We claim that at time $t$, the value of the
variable ${\mathsf{LastEvent}}$ must be ${\mathsf{UP}}$. Suppose not. Let
$t^{\prime}$ be the value of ${\mathsf{LastTime}}$ at time $t$ (i.e.,
$t^{\prime}$ is the last time before and including $t$ when an ${\mathsf{UP}}$
or a ${\mathsf{DOWN}}$ occurred). Since a ${\mathsf{DOWN}}$ event happened at
time $t^{\prime}$, ${\widetilde{x}_{v,j,{t^{\prime}}}}<h$. Since
$\widetilde{x}_{v,j,t}\geq h$, an ${\mathsf{UP}}$ event must occur during
$(t^{\prime},t]$, a contradiction. Therefore must have added an interval
containing time $t$ to ${\mathbf{I}}_{v,j}(h)$. Thus,
$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$ gets increased during each
such iteration, i.e., $\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}\geq
r>\widetilde{x}_{v,j,t}-1$. This proves the first inequality in (7).

We now prove the second inequality. Let $h$ be an integer satisfying
$h\geq\widetilde{x}_{v,j,t}+\nicefrac{{\varepsilon}}{{2}}.$ Consider the
iteration of the for loop in Algorithm 2 for this particular value of $h$. We
claim that the value of the variable ${\mathsf{LastEvent}}$ at time $t$ must
be ${\mathsf{DOWN}}$. Suppose not, and let $t^{\prime}$ denote the value of
the variable ${\mathsf{LastTime}}$. Then an ${\mathsf{UP}}$ happened at time
$t^{\prime}$ and so ${\widetilde{x}_{v,j,{t^{\prime}}}}\geq h$. Since
${\widetilde{x}_{v,j,{t}}}\leq h-\nicefrac{{\varepsilon}}{{2}}$, a
${\mathsf{DOWN}}$ event must have happened during $(t^{\prime},t]$, a
contradiction. Hence, we do not add any interval containing time $t$ to the
set ${\mathbf{I}}_{v,j}(h)$. Therefore,
$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}<\widetilde{x}_{v,j,t}+\nicefrac{{\varepsilon}}{{2}}$,
which proves the second inequality in (7). ∎

The next lemma establishes the key properties of the variables
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ and
$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$.

######  Lemma 4.2.

The following properties hold the for the variables
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$:

  1. (i)

(Cost) The LP cost increases by at most $O(\ell/\varepsilon)$ when the
original variables $y_{v,j,I}$ are replaced by the new variables
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$:

$\sum_{v,j,I}W_{j}\cdot{\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}\leq
O(\ell/\varepsilon)\cdot\sum_{v,j,I}W_{j}\cdot y_{v,j,I}.$

  2. (ii)

(Covering) The variables ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$
satisfy the scaled covering constraints of (LP2)

$\sum_{j,I:t\in
I}{\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}\geq\ell\quad\forall t.$

  3. (iii)

(Packing) The variables ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$
approximately satisfy the packing constraints of (LP2):

$\sum_{v,I:t\in
I}{\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}\leq(2+\varepsilon)\ell
k_{j}\quad\forall j\in[\ell],t.$

###### Proof.

We first prove the cost bound: the cost of the solution
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ is the weight of all
intervals added to the sets ${\mathbf{I}}_{v,j}(h)$ for all $v,j,h$. I.e.,

$\displaystyle\sum_{v,j,I}W_{j}\cdot{\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}=\sum_{v,j}W_{j}\cdot\sum_{h\in[\ell]}|{\mathbf{I}}_{v,j}(h)|.$
(8)

Fix a vertex $v$ and indices $j,h$. For a non-negative number $x$, and non-
negative integer $h$, define the _$h$ -level truncation_ of $x$ to be
${\mathsf{trunc}}_{h}(x):=\min(1,(x-h)^{+})$, where $(a)^{+}:=\max(a,0)$ for
any real $a$. Observe that $x=\sum_{h\geq 0}{\mathsf{trunc}}_{h}(x)$. In fact,
for any two non-negative integers $x$ and $y$:

$\displaystyle|x-y|=\sum_{h^{\prime}\geq
0}|{\mathsf{trunc}}_{h^{\prime}}(x)-{\mathsf{trunc}}_{h^{\prime}}(y)|.$ (9)

Now let $I_{1}=[s_{1},t_{1}),\ldots,I_{u}=[s_{u},t_{u})$ be the intervals
added to ${\mathbf{I}}_{v,j}(h)$ (in left to right order). Define $t_{0}=0$.
We know that for any $i\in[u]$, an ${\mathsf{UP}}$ happens at $s_{u}$ and a
${\mathsf{DOWN}}$ happens at $t_{u}$. Therefore,
${\mathsf{trunc}}_{h}({\widetilde{x}_{v,j,{s_{u}}}})-{\mathsf{trunc}}_{h}({\widetilde{x}_{v,j,{t_{u-1}}}})\geq\nicefrac{{\varepsilon}}{{2}}$.
Hence,

$\displaystyle\varepsilon W_{j}/2\cdot|{\mathbf{I}}_{v,j}(h)|$
$\displaystyle\leq
W_{J}\cdot\sum_{i=1}^{u}|{\mathsf{trunc}}_{h}({\widetilde{x}_{v,j,{s_{u}}}})-{\mathsf{trunc}}_{h}({\widetilde{x}_{v,j,{t_{u-1}}}})|$
$\displaystyle\leq
W_{j}\cdot\sum_{t^{\prime}=1}^{T}|{\mathsf{trunc}}_{h}({\widetilde{x}_{v,j,{t-1}}})-{\mathsf{trunc}}_{h}(\widetilde{x}_{v,j,t})|,$

where the last inequality follows from triangle inequality. Summing over all
$h$ and using (9), we get

$\varepsilon W_{j}/2\cdot{\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}\leq
W_{j}\cdot\sum_{t^{\prime}=1}^{T}|{\widetilde{x}_{v,j,{t-1}}})-\widetilde{x}_{v,j,t}|.$

Summing over all vertices $v$ and indices $j\in[\ell]$, we see that the cost
of the solution ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ is at most
$2/\varepsilon$ times that of ${\widetilde{y}}_{v,j,I}$. Finally, the fact
that ${\widetilde{y}}_{v,j,I}$ are obtained by scaling $y_{v,j,I}$ by a factor
$(2+\nicefrac{{\varepsilon}}{{2}})\ell$, we get the desired bound on the cost
of ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ solution.

Next, we prove the covering property. Since $x_{v,j,t}$ is a feasible solution
to LP2, we have for any time $t$:

$\sum_{j}x_{\sigma_{t},j,t}\geq 1,\text{ and therefore,
}\sum_{j}{\widetilde{x}_{\sigma_{t},j,t}}\geq(2+\nicefrac{{\varepsilon}}{{2}})\ell.$

Using Lemma 4.1, we have
${\widetilde{x}_{\sigma_{t},j,t}}<{\accentset{\rule{2.79996pt}{0.8pt}}{x}_{\sigma_{t},j,t}}+1$,
so

$\sum_{j\in\ell}\left({\accentset{\rule{2.79996pt}{0.8pt}}{x}_{\sigma_{t},j,t}}+1\right)>(2+\nicefrac{{\varepsilon}}{{2}})\ell,\text{
and therefore,
}\sum_{j}{\accentset{\rule{2.79996pt}{0.8pt}}{x}_{\sigma_{t},j,t}}>\ell.$

Finally, we prove the packing property. Since $x_{v,j,t}$ is a feasible
solution to the LP, we have for any $j\in[\ell]$ and time $t$,

$\sum_{v}x_{v,j,t}\leq k_{j},\text{ and therefore,
}\sum_{v}\widetilde{x}_{v,j,t}\leq(2+\nicefrac{{\varepsilon}}{{2}})\ell
k_{j}.$

Again Lemma 4.1 gives
$\widetilde{x}_{v,j,t}>\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}-\nicefrac{{\varepsilon}}{{2}}$,
which implies

$\sum_{j}\left(\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}-\nicefrac{{\varepsilon}}{{2}}\right)^{+}<(2+\nicefrac{{\varepsilon}}{{2}})\ell
k_{j}.$ (10)

Since $\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$ is a nonnegative
integer,

$\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}>0\implies\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}\geq
1\stackrel{{\scriptstyle\small{\mbox{\lx@cref{creftypecap~refnum}{lem:range}}}}}{{\implies}}\widetilde{x}_{v,j,t}>\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}-\nicefrac{{\varepsilon}}{{2}}\geq
1-\nicefrac{{\varepsilon}}{{2}}.$

Since $\sum_{v}\widetilde{x}_{v,j,t}\leq k_{j}$, it follows that the number of
locations $v$ for which $\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}>0$ is
at most $\frac{k_{j}}{1-\nicefrac{{\varepsilon}}{{2}}}<2k_{j}$, if
$\varepsilon<1$. Using this fact in Equation 10, we get

$\displaystyle\sum_{v}\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}$
$\displaystyle=\sum_{v:\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}>0}\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}=\sum_{v:\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}>0}\left(\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}-\nicefrac{{\varepsilon}}{{2}}\right)+\sum_{v:\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}>0}\nicefrac{{\varepsilon}}{{2}}$
$\displaystyle\leq\sum_{v}\left(\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}-\nicefrac{{\varepsilon}}{{2}}\right)^{+}+2k_{j}\cdot\nicefrac{{\varepsilon}}{{2}}\leq(2+\nicefrac{{\varepsilon}}{{2}})\ell
k_{j}+\varepsilon k_{j}.$

Since $\ell\geq 2$ (otherwise, we have the unweighted problem), we get

$\sum_{v}\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}\leq(2+\varepsilon)\ell
k_{j}.\qed$

###  4.2 Stage II: Weighted Interval Cover

In the second stage of the rounding algorithm, we first scale the (integer-
valued) variables ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ down by a
factor of $\ell$ to obtain new variables $y_{v,j,I}^{*}$:

$\displaystyle
y_{v,j,I}^{*}:={\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}/\ell\text{ and
therefore, }x_{v,j,t}^{*}=\sum_{I:t\in
I}y_{v,j,I}^{*}=\accentset{\rule{2.79996pt}{0.8pt}}{x}_{v,j,t}/\ell.$ (11)

Our goal is to round the fractional variables $y_{v,j,I}^{*}$ to $\\{0,1\\}$
values. In fact, our rounding will ensure that if the rounded value equals $1$
then $y_{v,j,I}^{*}>0$. Since
${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}$ is integral, the packing
property in Lemma 4.2 implies that for any time $t$, vertex $v$, and index
$j\in[\ell]$, there are at most $(2+\varepsilon)\ell k_{j}$ intervals $I\ni t$
for which ${\accentset{\rule{2.79996pt}{0.8pt}}{y}}_{v,j,I}>0$. The rounding
property of our algorithm will ensure that the final integral solution, which
lies in the support of $y_{v,j,I}^{*}$, will also satisfy that there are at
most $(2+\varepsilon)\ell k_{j}$ intervals containing any time $t$. Since we
are allowed a resource augmentation of $(2+\varepsilon)\ell$ factor in the
number of servers of weight $W_{j}$, we can serve the requests with the set of
available servers. Henceforth, we can ignore the packing constraint (6) for
our rounded solution. As a result, the relaxation LP2 decouples into $n$
independent relaxations, one for each location $v\in V$.

In this decoupled instance, we get the following LP relaxation for each
location $v$, where for each class $j\in[\ell]$, we define
${\mathbf{I}}_{v,j}:=\\{I\mid y_{v,j,I}^{*}>0\\}$ as the set of intervals $I$
with a nonzero value of $y_{v,j,I}^{*}$ and $\mathcal{R}(v)$ as the set of
times $t$ when $v$ is requested:

$\displaystyle\min\nicefrac{{1}}{{2}}\sum_{j\in[\ell]}W_{j}\cdot\sum_{I\in{\mathbf{I}}_{v,j}}$
$\displaystyle y_{v,j,I}$ (LPv) $\displaystyle\text{ s.t.
}\sum_{j}\sum_{I\in{\mathbf{I}}_{v,j}:t\in I}y_{v,j,I}$ $\displaystyle\geq 1$
$\displaystyle\forall t\in\mathcal{R}_{v}$ $\displaystyle y_{v,j,I}$
$\displaystyle\geq 0.$

By the covering property of Lemma 4.2, the variables $y_{v,j,I}^{*}$ defined
in (11) are feasible solutions for (LPv) for all locations $v$. Furthermore,
by the lemma’s cost property (and the scaling down by $\ell$), the total cost
$\sum_{v}\sum_{j}W_{j}\cdot\sum_{I}y_{v,j,I}^{*}$ is at most
$O(1/\varepsilon)$ times the optimal cost of (LP2).

Finally, the constraint matrix for (LPv) satisfies the consecutive-ones
property: if the constraints are ordered chronologically, then a variable
$y_{v,j,I}$ appears in the constraints corresponding to times $t\in I$ where
$\sigma_{t}=v$, which is a contiguous subsequence of all times $t$ where
$\sigma_{v}=j$. Constraint matrices with this property are totally unimodular
(see, e.g., [FG65]). Therefore, each of the solutions
$\\{y_{v,j,I}^{*}:j\in[\ell],I\in{\mathbf{I}}_{v,j}\\}$ for LPv can be rounded
to a feasible integral solution without any increase in cost, which proves
Theorem 1.3.

##  5 Online Algorithm

In this section, we describe an efficient online algorithm for Weighted
$k$-Server and prove the following result: See 1.4

We begin by re-writing the LP relaxation (LP2) in terms of the “anti-page”
variables, as in [BBN12]. Recall that (LP2) has variables $y_{v,j,I}$
representing the (fractional) weight $W_{j}$ server mass present at location
$v$ during the interval $I$; instead we first rewrite it in terms of the
“page” variables $x_{v,j,t}$, which denote the total amount of weight $W_{j}$
server mass at location $v$ at time $t$, as given in (4). The objective of
this LP in terms of $x_{v,j,t}$ is:

$\sum_{v,j,I}W_{j}\cdot
y_{v,j,I}=\sum_{v,j,I}W_{j}\cdot(x_{v,j,t}-x_{v,j,t^{-}})^{+}.$

We can constrain any algorithm to values $x_{v,j,t}\in[0,1]$ for all $v,j,t$
(since having multiple servers at a location is not beneficial). This allows
us to work with non-negative _anti-page_ variables $z_{v,j,t}:=1-x_{v,j,t}$.
The objective, now rewritten in terms of these new variables $z_{v,j,t}$,
becomes:

$\displaystyle\sum_{v,j,I}W_{j}\cdot(x_{v,j,t}-x_{v,j,t^{-}})^{+}=\sum_{v,j,I}W_{j}\cdot(z_{v,j,t^{-}}-z_{v,j,t})^{+}.$
(12)

We shall also maintain the following invariant for each server weight $W_{j}$
and time $t$:

$\displaystyle\sum_{v}x_{v,j,t}=k_{j}\qquad\iff\qquad\sum_{v}z_{v,j,t}=n-k_{j}~{}\quad\forall
j,t.$ (13)

We write the covering constraint (5) (or equivalently (2)) in terms of
$z_{v,j,t}$ as:

$\sum_{j}z_{\sigma_{t},j,t}\leq\ell-1$ (14)

The algorithm follows the standard relax-and-round paradigm in the online
setting. The first step is to compute a feasible fractional solution to an LP
consisting of objective (12) and constraints (13) and (14), in an online
setting. We show in §5.1 that we can find a fractional solution that uses
$O(\ell k_{j})$ servers of weight $W_{j}$ for each class $j$, and has a
competitive ratio of $O(\ell^{2})$. The second step is to give an online
rounding algorithm to convert this fractional solution to an integral
solution: our rounding algorithm given in §5.2 uses the standard online
rounding algorithm for the paging problem and increases the cost of the
solution by a constant factor.

###  5.1 Online Fractional Algorithm

In this section, we give an online algorithm for maintaining a fractional
solution to the LP involving $z_{v,j,t}$ variables. We obtain the following
result:

######  Theorem 5.1.

There is a deterministic (polynomial time) online fractional algorithm that
maintains the condition that for every request time $t$, there exists an index
$j\in[\ell]$ such that there is unit server mass of weight $W_{j}$ at location
$\sigma_{t}$ at time $t$. The algorithm uses $2\ell k_{j}$ servers of weight
$W_{j}$ for each $j\in[\ell]$, and whose cost is at most $O(\ell^{2}\log\ell)$
times that of an optimal fractional solution.

Note that the condition in the theorem is stronger than (14), the feasibility
condition for (LP2), because we are using server from a single weight class to
service this request.

Consider a time $t$, and the request arriving at location $\sigma_{t}$. We
first set $z_{v,j,t}=z_{v,j,t^{-}}$ for all $v\in V,j\in\ell$. Now the
algorithm moves fractional server mass to $\sigma_{t}$ until a relaxed version
of the covering constraint (14) for time $t$ gets satisfied. The relaxed
constraint is given by

$\exists j\in[\ell]\text{ such that }z_{\sigma_{t},j,t}\leq
1-\frac{1}{2\ell}.$ (15)

Indeed, if the constraint is violated, then for each vertex $v\neq\sigma_{t}$
and each $j\in[\ell]$, if $v$ has non-zero server mass of weight $W_{j}$
(i.e., $z_{v,j,t}<1$), then the algorithm moves server mass of weight $W_{j}$
from $v$ to $\sigma_{t}$ using the following differential equation. (The
derivative is with respect to a variable $s$ which starts from 0 and increases
at uniform rate.)

$\dot{z}_{v,j,t}=\frac{1}{W_{j}|S_{j}|}\cdot\left(z_{v,j,t}+\delta\right)~{}\quad\forall
j\in[\ell],\forall v\in S_{j}.$ (16)

Here, $S_{j}\subseteq V$ denotes the instantaneous set of locations (i.e., at
the current value of the variable $s$) that have $z_{v,j,t}<1$, not including
the location $\sigma_{t}$, and $\delta>0$ is a parameter that we shall fix
later. Correspondingly, we reduce $z_{\sigma_{t},j,t}$ by the total amount of
server mass of weight $W_{j}$ entering $\sigma_{t}$:

$\dot{z}_{\sigma_{t},j,t}=-\frac{1}{W_{j}|S_{j}|}\cdot\sum_{v\in
S_{j}}\left(z_{v,j,t}+\delta\right)~{}\quad\forall j\in[\ell].$ (17)

Note that server mass is moved away other locations and into location
$\sigma_{t}$ only if $z_{\sigma_{t},j,t}>1-\frac{1}{2\ell}$ for all $j$. Since
$z_{\sigma_{t},j,t}\leq 1$ for all $j$, it follows that
$z_{v,j,t}\in[1-\frac{1}{2\ell},1]$ for all $j,t$. Hence,

$z_{v,j,t}\geq 1-\frac{1}{2\ell}\text{ for all
}j,t\quad\implies\quad|S_{j}|\geq 2\ell k_{j}-1\geq\frac{3\ell k_{j}}{2}\geq
3\text{ for all }j,t,$ (18)

since $\ell\geq 2,k_{j}\geq 1$.

To analyze the algorithm, we use a potential function $\Phi$. The potential
function depends on the offline (integral) optimal solution—let us call it
${\cal O}$, and let $\text{opt}_{v,j,t}$ be the indicator variable for the
location $v$ containing a server of weight $W_{j}$ at time $t$. The potential
at time $t$ is defined as follows:

$\Phi(t):=\sum_{v,j:\text{opt}_{v,j,t}=0}W_{j}\cdot\ln\left(\frac{1+\delta}{z_{v,j,t}+\delta}\right).$

Let ${\textsf{cost}}(t)$ denote the algorithm’s server movement cost at time
$t$ and ${\textsf{cost}}^{{\cal O}}(t)$ denote the corresponding quantity for
the optimum solution ${\cal O}$. Our goal is to show that:

$\displaystyle\frac{{\textsf{cost}}(t)}{4\ell}+\Phi(t+1)-\Phi(t)\leq\ln(1+\nicefrac{{1}}{{\delta}})\cdot{\textsf{cost}}^{{\cal
O}}(t).$ (19)

The following properties of $\Phi(t)$ can verified easily:

  * •

Nonnegativity: $\Phi$ is always nonnegative, since $z_{v,j,t}\leq 1$.

  * •

Lipschitzness property: When the optimal solution moves a server of weight
$W_{j}$ from one location to another, the increase in $\Phi$ is at most
$W_{j}\cdot\ln(1+\nicefrac{{1}}{{\delta}})$.

The Lipschitzness property implies that (19) holds when ${\cal O}$ serves the
request at $\sigma_{t}$. It remains the analyze the cost and change in
potential when the algorithm changes its solution. Consider the process when
we transfer server mass to $\sigma_{t}$.

We first bound the online algorithm’s cost. Since all the weight classes incur
the same server movement cost while transferring to $\sigma_{t}$, the movement
cost is $\ell$ times the movement cost incurred while transferring servers of
a fixed class, say $j^{\star}$. The latter is at most

$\displaystyle W_{j^{\star}}\sum_{v\in
S_{j^{\star}}}\dot{z}_{v,{j^{\star}},t}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:rate}}}{{=}}\frac{1}{|S_{j^{\star}}|}\sum_{v\in
S_{j^{\star}}}(z_{v,{j^{\star}},t}+\delta)\quad=\frac{|S_{j^{\star}}|+1-k_{j^{\star}}+\delta|S_{j^{\star}}|}{|S_{j^{\star}}|}\leq
1+\delta.$ (20)

Thus, the upper bound on the $\frac{{\textsf{cost}}(t)}{4\ell}$ term in the
LHS of (19) is at most $\frac{1+\delta}{4}\leq\nicefrac{{1}}{{3}}$ provided
$\delta\leq\nicefrac{{1}}{{3}}$.

Next, we lower bound the rate of decrease of potential $\Phi$. We begin by
bounding the rate of decrease in potential due to because of server mass
leaving all locations except $\sigma_{t}$:

$\displaystyle\Delta^{-}$
$\displaystyle=-\sum_{j\in[\ell],v\neq\sigma_{t}:\text{opt}_{v,j,t}=0}\frac{W_{j}}{z_{v,j,t}+\delta}\cdot\dot{z}_{v,j,t}\quad\stackrel{{\scriptstyle\eqref{eq:rate}}}{{=}}-\sum_{j,v\in
S_{j}:\text{opt}_{v,j,t}=0}\frac{1}{z_{v,j,t}+\delta}\cdot\frac{z_{v,j,t}+\delta}{|S_{j}|}$
$\displaystyle=-\sum_{j}\frac{|\\{v\in
S_{j}:\text{opt}_{v,j,t}=0\\}|}{|S_{j}|}\quad\stackrel{{\scriptstyle\eqref{eq:z-lb}}}{{\leq}}-\sum_{j}\frac{|S_{j}|-k_{j}}{|S_{j}|}\leq-\ell\left(1-\frac{2}{3\ell}\right)=-\ell+\nicefrac{{2}}{{3}}.$
(21)

Next, we bound the rate of increase in potential due to server classes
$j\not=j^{*}$ because of server mass entering $\sigma_{t}$:

$\displaystyle\Delta^{+}$
$\displaystyle=\sum_{j\not=j^{*}}\frac{W_{j}}{z_{\sigma_{t},j,t}+\delta}\cdot\dot{z}_{\sigma_{t},j,t}\quad\stackrel{{\scriptstyle\eqref{eq:rate}}}{{=}}\sum_{j\not=j^{*},v\in
S_{j}}\frac{W_{j}}{z_{\sigma_{t},j,t}+\delta}\cdot\frac{z_{v,j,t}+\delta}{|S_{j}|W_{j}}$
$\displaystyle=\sum_{j\not=j^{*}}\frac{\sum_{v\in
S_{j}}(z_{v,j,t}+\delta)}{|S_{j}|(z_{\sigma_{t},j,t}+\delta)}\quad=\sum_{j\not=j^{*}}\frac{(|S_{j}|-k_{j}+(1-z_{\sigma_{t},j,t}))+\delta\cdot|S_{j}|}{|S_{j}|(z_{\sigma_{t},j,t}+\delta)}\;$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:z-lb}}}{{\leq}}\sum_{j\not=j^{*}}\frac{(|S_{j}|-k_{j}+\nicefrac{{1}}{{2\ell}})+\delta\cdot|S_{j}|}{|S_{j}|(1-\nicefrac{{1}}{{2\ell}}+\delta)}\quad\stackrel{{\scriptstyle\eqref{eq:z-lb}}}{{\leq}}\sum_{j\neq{j^{\star}}}\frac{1-\nicefrac{{2}}{{3\ell}}+\nicefrac{{1}}{{6\ell}}+\delta}{1-\nicefrac{{1}}{{2\ell}}+\delta}\quad\leq\ell-1,$

provided $\delta=\nicefrac{{1}}{{2\ell}}$. Combining with (21), we see that
the overall change in potential is
$\Delta^{-}+\Delta^{+}\leq-\nicefrac{{1}}{{3}}$. Consequently, we get that the
change in potential pays for the increase in the algorithm’s cost (divided by
$4\ell$)—which shows (19)—when the fractional solution changes.

This implies that we have an algorithm for maintaining $z_{v,j,t}$ that
satisfies (15). In terms of the competitive ratio, the algorithm loses $4\ell$
in (19) and $\ln(1+\nicefrac{{1}}{{\delta}})=O(\log\ell)$ in the Lipschitzness
of the potential function. Note that (15) implies that for all $t$, there
exists $j$ such that $x_{\sigma_{t},j,t}\geq\frac{1}{2\ell}$. We scale the
fractional variables to obtain $\widetilde{x}_{v,j,t}:=\min(2\ell
x_{v,j,t},1)$; then, for all $t$, there exists $j$ such that
$\widetilde{x}_{\sigma_{t},j,t}=1$. Note that this satisfies the condition in
Theorem 5.1. Equivalently, the corresponding “anti-page” variables
$\widetilde{z}_{v,j,t}:=1-\widetilde{x}_{v,j,t}$ satisfy the following
condition for all $t$:

$\exists j\text{ such that }\widetilde{z}_{\sigma_{t},j,t}=0.$ (22)

The last scaling step creates a resource augmentation of $2\ell$, and
increases the competitive ratio to $O(\ell^{2}\log\ell)$. This completes the
proof of Theorem 5.1.

###  5.2 Rounding the Fractional Solution Online

We round the fractional solution for each weight class $j$ separately. Let
$T_{j}$ represent the request times $t$ when (22) is satisfied by weight class
$j$. Note that the solution $\widetilde{z}_{v,j,t}$ for weight class $j$
represents a feasible fractional solution for an instance of the paging
problem with $2\ell k_{j}$ cache slots, where there is a page request for each
time $t\in T_{j}$ at location $\sigma_{t}$.

We now invoke the following known online rounding algorithm for the paging
problem separately in each weight class $j$ to complete the proof of Theorem
1.4.

######  Lemma 5.2.

[BBK99] There is a randomized (polynomial time) online algorithm that converts
any feasible fractional solution for an instance of the Paging problem to an
integral solution using the same number of cache slots, and incurs constant
times the cost of the fractional solution.

##  6 Discussion

In this work, we have given the first efficient offline and online algorithms
with non-trivial guarantees for Weighted $k$-Server. Several interesting
problems remains open:

  1. 1.

For the case of two distinct weight classes, we show in Section 2 that it is
UG-Hard to obtain an $\Omega(N^{c})$-approximation algorithm for some constant
$c>0$, even with $(2-\varepsilon)$-resource augmentation. Can we extend such a
hardness result to more weight classes? For example, can we show that for
three distinct weight classes, it is UG-Hard to obtain a $C$-approximation
algorithm for any constant $C$, even with $(3-\varepsilon)$-resource
augmentation? The principal reason why our hardness proof for $\ell=2$ does
not extend here is because one needs to recursively cycle through all subsets
(of a certain size) of $V$ to create an integrality gap instance for the
natural LP relaxation. If the size of these subsets is large, then the length
of the input becomes very large. If the size of these subsets is small, then
it is not clear how to extend this to a hardness proof.

  2. 2.

In Section 4, we give an offline constant approximation algorithm which
requires slightly more than $2\ell$-resource augmentation. Can we get a
constant approximation algorithm (or even an optimal algorithm) with exactly
$\ell$-resource augmentation? We conjecture that the integrality gap of LP is
constant (or even $1$) if the integral solution is allowed $\ell$-resource
augmentation.

  3. 3.

In the online case, we give a $O(\ell^{2}\log\ell)$-competitive algorithm with
$2\ell$-resource augmentation in Section 5. Can we get a constant-competitive
algorithm with $O(\ell)$-resource augmentation, i.e., a result in the same
vein as our offline algorithm?

## References

  * [AC21] Nikhil Ayyadevara and Ashish Chiplunkar.  The randomized competitive ratio of weighted $k$-server is at least exponential.  In 29th Annual European Symposium on Algorithms, volume 204 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 9, 11. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021.
  * [BBBT99] Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins.  A ${\rm polylog}(n)$-competitive algorithm for metrical task systems.  In STOC ’97 (El Paso, TX), pages 711–719. ACM, New York, 1999.
  * [BBK99] Avrim Blum, Carl Burch, and Adam Kalai.  Finely-competitive paging.  In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA, pages 450–458. IEEE Computer Society, 1999.
  * [BBMN15] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor.  A polylogarithmic-competitive algorithm for the _k_ -server problem.  J. ACM, 62(5):40:1–40:49, 2015.
  * [BBN10] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  Metrical task systems and the $k$-server problem on HSTs.  In Automata, languages and programming. Part I, volume 6198 of Lecture Notes in Comput. Sci., pages 287–298. Springer, Berlin, 2010\.
  * [BBN12] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  A primal-dual randomized algorithm for weighted paging.  J. ACM, 59(4):19, 2012.
  * [BCL+18] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry.  k-server via multiscale entropic regularization.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3–16. ACM, 2018.
  * [BCLL21] Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee.  Metrical task systems on trees via mirror descent and unfair gluing.  SIAM J. Comput., 50(3):909–923, 2021.
  * [BDBK+94] S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson.  On the power of randomization in on-line algorithms.  Algorithmica, 11(1):2–14, 1994.
  * [BEJK19] Nikhil Bansal, Marek Eliás, Lukasz Jez, and Grigorios Koumoutsos.  The (_h, k_)-server problem on bounded depth trees.  ACM Trans. Algorithms, 15(2):28:1–28:26, 2019.
  * [BEK17] Nikhil Bansal, Marek Eliáš, and Grigorios Koumoutsos.  Weighted $k$-server bounds via combinatorial dichotomies.  In 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, pages 493–504. IEEE Computer Soc., Los Alamitos, CA, 2017.
  * [BEY98] Allan Borodin and Ran El-Yaniv.  Online Computation and Competitive Analysis.  Cambridge University Press, USA, 1998.
  * [BGMN19] Niv Buchbinder, Anupam Gupta, Marco Molinaro, and Joseph (Seffi) Naor.  k-servers with a smile: Online algorithms via projections.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 98–116. SIAM, 2019.
  * [BLS92] Allan Borodin, Nathan Linial, and Michael E. Saks.  An optimal on-line algorithm for metrical task system.  J. Assoc. Comput. Mach., 39(4):745–763, 1992.
  * [CL22] Christian Coester and James R. Lee.  Pure entropic regularization for metrical task systems.  Theory Comput., 18:Paper No. 23, 24, 2022.
  * [CV20] Ashish Chiplunkar and Sundar Vishwanathan.  Randomized memoryless algorithms for the weighted and the generalized $k$-server problems.  ACM Trans. Algorithms, 16(1):Art. 14, 28, 2020.
  * [FG65] D. R. Fulkerson and O. A. Gross.  Incidence matrices and interval graphs.  Pacific Journal of Mathematics, 15(3):835 – 855, 1965.
  * [FR94] Amos Fiat and Moty Ricklin.  Competitive algorithms for the weighted server problem.  Theoret. Comput. Sci., 130(1):85–99, 1994.
  * [KP95a] Bala Kalyanasundaram and Kirk Pruhs.  Speed is as powerful as clairvoyance.  In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 214–221. IEEE Computer Society, 1995.
  * [KP95b] Elias Koutsoupias and Christos H. Papadimitriou.  On the k-server conjecture.  J. ACM, 42(5):971–983, 1995.
  * [Lee18] James R. Lee.  Fusible hsts and the randomized k-server conjecture.  In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 438–449. IEEE Computer Society, 2018.
  * [MMS90] Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator.  Competitive algorithms for server problems.  J. Algorithms, 11(2):208–230, 1990.
  * [ST85] Daniel Dominic Sleator and Robert Endre Tarjan.  Amortized efficiency of list update and paging rules.  Commun. ACM, 28(2):202–208, 1985.
  * [You91] Neal E. Young.  On-line caching as cache size varies.  In Alok Aggarwal, editor, Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 28-30 January 1991, San Francisco, California, USA, pages 241–250. ACM/SIAM, 1991.


* [24] Andrew V. Sutherland and David Zywina.  Modular curves of prime-power level with infinitely many rational points.  Algebra & Number Theory, 11:1199–1229, 2017.


# Polarization and energy ellipsoids for an introductory visualization of
tensors

Danilo T. Alves<EMAIL_ADDRESS>Faculdade de Física, Universidade Federal do
Pará, 66075-110, Belém, Pará, Brazil  Lucas Queiroz<EMAIL_ADDRESS>Instituto Federal de Educação, Ciência e Tecnologia do Pará, Campus Marabá
Rural, 68508-970, Marabá, Pará, Brazil  Faculdade de Física, Universidade
Federal do Pará, 66075-110, Belém, Pará, Brazil  Jeferson Danilo L. Silva
<EMAIL_ADDRESS>Faculdade de Engenharia da Computação e Telecomunicações,
Instituto de Tecnologia, Universidade Federal do Pará, 66075-110, Belém, Pará,
Brazil

(August 28, 2024)

###### Abstract

In The Feynman Lectures on Physics is discussed an introduction to tensors,
specifically a way of “visualizing” the polarization tensor, by means of the
energy ellipsoid, which is drawn by the electric fields which produce the same
polarization energy density in an anisotropic crystal. Here, we discuss an
alternative way of visualizing the polarization tensor, by means of the
polarization ellipsoid, which is based on the ideas of Lamé’s stress ellipsoid
and is drawn by the polarization vectors produced by electric fields having
the same magnitude. We compare both ellipsoids as a first introductory way of
visualizing the polarization tensor.

##  I Introduction

Feynman, in Ref. [1], presents a didactic approach to introduce the
description of tensors, using the dependence of the induced polarization of an
anisotropic crystal on the direction of the applied electric field. He also
presents the energy ellipsoid as a way of “visualizing” the polarizability
tensor. The energy ellipsoid is drawn by electric fields $\bf{E}$ which
produce the same polarization energy density $u_{P}$ in the anisotropic
crystal. In the present paper, we discuss the polarization ellipsoid, which is
drawn by polarizations vectors $\bf{P}$ (induced dipole moment per unit
volume) produced by electric fields $\bf{E}$, with a given constant magnitude
$E$, applied in different directions on an anisotropic crystal. This
polarization ellipsoid is based on the ideas of the Lamé’s stress ellipsoid
[2].

##  II The Energy Ellipsoid

In order to introduce the energy ellipsoid, Feynman starts by discussing the
problem of the polarization of a crystal. He obtains that the energy per unit
volume required to polarize a crystal is [1]

$u_{P}=\frac{1}{2}\mathbf{E}\cdot\mathbf{P},$ (1)

where $\mathbf{E}$ is the electric field applied and $\mathbf{P}$ is the
induced dipole moment per unit volume. The vectors $\mathbf{E}$ and
$\mathbf{P}$ are related by the polarizability tensor as

$P_{i}=\sum_{j}\alpha_{ij}E_{j},$ (2)

where $i$ and $j$ represent either $x$, $y$, or $z$, and $\alpha_{ij}$
represents the elements of the tensor of polarizability. Thus, $u_{P}$ can be
rewritten in terms only of the components of $\mathbf{E}$, namely

$u_{P}=\frac{1}{2}\sum_{i}\sum_{j}\alpha_{ij}E_{i}E_{j}.$ (3)

Let us consider the particular case of an electric field applied with only $x$
and $y$ components and, since $\alpha_{yx}=\alpha_{xy}$ [1], one can obtain
all values of $E_{x}$ and $E_{y}$ that correspond to a given amount of energy
$u_{0}$ by solving the equation [1]

$\alpha_{xx}E_{x}^{2}+2\alpha_{xy}E_{x}E_{y}+\alpha_{yy}E_{y}^{2}=2u_{0}.$ (4)

According to Feynman, this quadratic equation “must be an ellipse, rather than
a parabola or a hyperbola, because the energy for any field is always positive
and finite”. Each point of this ellipse — the energy ellipse — corresponds to
an electric field $\mathbf{E}$ that polarizes the crystal with the same energy
density $u_{0}$. If all three components are included in Eq. (3), the electric
field $\mathbf{E}$ in any direction gives a point which will be on the surface
of an ellipsoid, the so-called energy ellipsoid.

For simplicity, let us consider $\alpha_{xy}=0$, so that Eq. (4) becomes:

$\alpha_{xx}E_{x}^{2}+\alpha_{yy}E_{y}^{2}=2u_{0}.$ (5)

A visual representation of this energy ellipse is given in Figs. 1(a)-1(d),
where we show some different vectors $\mathbf{E}$, which define points on the
energy ellipse, also indicating that the value of $u_{0}$ is the same in each
case. Notice that, in the example discussed in Fig. 1, the polarizability is
greater in the $x$-direction ($\alpha_{xx}>\alpha_{yy}$), but the major axis
of the energy ellipse is perpendicular to this direction (coinciding with the
$y$-axis). Since the energy ellipse is built by electric fields producing the
same energy of polarization, its major axis does not coincide with the
direction where the polarizability of the crystal is the greatest.

(a) (b) (c) (d)

Figure 1:  Plots of Eq. (4), considering $u_{0}=1$, $\alpha_{xx}=0.90$ and
$\alpha_{yy}=0.45$ (so that $\alpha_{xx}=2\alpha_{yy}$). In each plot, we show
simultaneously the energy $u_{0}$ (the value is the same) and a vector
$\mathbf{E}$ with its magnitude indicated. The electric fields $\bf{E}$ have
different magnitudes, but they all polarize the crystal with the same energy
$u_{0}$, and each one defines a point on the energy ellipse.

##  III The Polarization Ellipsoid

Following with the particular case of an electric field applied with only $x$
and $y$ components, let us now consider the polarization ellipse, which is
drawn by the polarization vectors $\bf{P}$ produced by electric fields which
have the same magnitude $E$. From $E^{2}=E_{x}^{2}+E_{y}^{2}$, and using Eq.
(2), we obtain all values of $P_{x}$ and $P_{y}$ that correspond to a given
$E$ by solving the equation

$E^{2}=\frac{\alpha_{xy}^{2}+\alpha_{yy}^{2}}{(\alpha_{xx}\alpha_{yy}-\alpha_{xy}^{2})^{2}}P_{x}^{2}-\frac{2\alpha_{xy}(\alpha_{xx}+\alpha_{yy})}{(\alpha_{xx}\alpha_{yy}-\alpha_{xy}^{2})^{2}}P_{x}P_{y}+\frac{\alpha_{xy}^{2}+\alpha_{xx}^{2}}{(\alpha_{xx}\alpha_{yy}-\alpha_{xy}^{2})^{2}}P_{y}^{2}.$
(6)

If all three components are included, the vector $\mathbf{P}$ in any direction
gives a point which will be on the surface of an ellipsoid, here called the
polarization ellipsoid.

For simplicity, let us consider again $\alpha_{xy}=0$. Then Eq. (6) takes the
form:

$E^{2}=\frac{1}{\alpha_{xx}^{2}}P_{x}^{2}+\frac{1}{\alpha_{yy}^{2}}P_{y}^{2}.$
(7)

A visual representation of this polarization ellipse is given in Figs.
2(a)-2(d). We show some different vectors $\mathbf{P}$, which define points on
the polarization ellipse, and simultaneously indicate $\mathbf{E}$ in each
figure (since $E$ is the same, the fields $\mathbf{E}$ describe a circle).
Moreover, in the example discussed in Fig. 2, the direction where the
polarizability is greater (the $x$-direction) coincides with the major axis of
the ellipse. Therefore, the polarization ellipse provides a visual indication
of the direction where the crystal is most “easily” polarizable, and the
greater the ratio between $\alpha_{xx}$ and $\alpha_{yy}$, the greater is its
eccentricity.

(a) (b) (c) (d)

Figure 2:  Plot of Eq. (7), considering $E=1$, $\alpha_{xx}=0.90$ and
$\alpha_{yy}=0.45$ (so that $\alpha_{xx}=2\alpha_{yy})$. In each plot, we show
simultaneously the vector $\mathbf{E}$ and the vector $\mathbf{P}$, with this
latter defining a point on the polarization ellipse (red line). In each
figure, $E$ is the same, so that the fields $\mathbf{E}$ describe a circle
(blue line).

##  IV Analysis and Final Remarks

Considering the polarization ellipse (Fig. 2), one can establish a direct
visual correlation of cause and effect between the vectors $\bf{E}$ and
$\bf{P}$: for example, during a didactic computer simulation, the appearance
of $\bf{E}$ can be directly connected to the appearance of $\bf{P}$, showing
that, in general, they do not have the same direction in an anisotropic
object. Moreover, the major axis of the polarization ellipse coincides with
the axis of the greatest value of the polarizability of the crystal ($x-$axis,
in the considered example). On the other hand, when constructing the energy
ellipse (Fig. 1), we do not have such a direct visual correlation between
$u_{0}$ and $\bf{E}$, and the major axis of the energy ellipse coincides with
the axis of smallest value of the polarizability ($y-$axis, in the example).
Taking into account all three components of $\bf{E}$, we conclude that the
polarization ellipsoid has some advantages over the energy ellipsoid as a
first introductory way of discussing the visualization of tensors.

###### Acknowledgements.

The authors thank Marcelo C. de Lima and Van Sérgio Alves for fruitful
discussions. L.Q. was supported by the Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior (CAPES) – Brasil, Finance Code 001. This work was
partially supported by CNPq – Brazil, Processo 408735/2023-6 CNPq/MCTI.

## References

  * Feynman  _et al._ [2006] R. Feynman, R. Leighton, and M. Sands,  _The Feynman Lectures on Physics_, Vol. II (Pearson/Addison-Wesley, 2006) Chap. 31.
  * Fung [1965] Y. Fung,  _Foundations of Solid Mechanics_, Prentice-Hall international series in dynamics, Vol. 1 (Kluwer Academic Publishers, 1965).