A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs

In the online List Update problem [3, 20, 21], the objective is to maintain a set of items stored in a linear list in response to a sequence of access requests. The cost of accessing a requested item is equal to its distance from the front of the list. After each request, an algorithm is allowed to rearrange the list by performing an arbitrary number of swaps of adjacent items. In the model introduced by Sleator and Tarjan in their seminal 1985 paper on competitive analysis [25], an algorithm can repeatedly swap the requested item with its preceding item at no cost. These swaps are called free. All other swaps are called paid and have cost $1$ each. As in other problems involving self-organizing data structures [7], the goal is to construct an online algorithm, i.e., operating without the knowledge of future requests. The cost of such an algorithm is compared to the cost of the optimal offline algorithm; the ratio of the two costs is called the competitive ratio and is subject to minimization.

Sleator and Tarjan proved that the algorithm Move-To-Front (Mtf), which after each request moves the requested item to the front of the list, is $2$-competitive [25]. This ratio is known to be optimal if the number of items is unbounded. Their work was the culmination of previous extensive studies of list updating, including experimental results, probabilistic approaches, and earlier attempts at amortized analysis (see [15] and the references therein).

As shown in subsequent work, Mtf is not unique – there are other strategies that achieve ratio $2$, such as TimeStamp [2] or algorithms based on work functions [9]. In fact, there are infinitely many algorithms that achieve ratio $2$ [13, 21].

Following [24], we will refer to the cost model of [25] as standard, and we will denote it here by ${\text{LUP}}_{\mathrm{S}}$. This model has been questioned in the literature for not accurately reflecting true costs in some implementations [24, 23, 22, 18], with the concept of free swaps being one of the main concerns.

A natural approach to address this concern, considered in some later studies (see, e.g., [24, 7, 21, 4, 12]), is simply to charge cost $1$ for any swap. We will call it here the uniform cost model and denote it ${\text{LUP}}_1$. A general lower bound of $3$ on the competitive ratio of deterministic algorithms for ${\text{LUP}}_1$ was given by Reingold et al.  [24]. Changing the cost of free swaps from $0$ to $1$ at most doubles the cost of any algorithm, so Mtf is no worse than $4$-competitive for ${\text{LUP}}_1$. Surprisingly, no algorithm is known to beat Mtf, i.e., achieve ratio lower than $4$.¹¹1The authors of [21] claimed an upper bound of $3$ for ${\text{LUP}}_1$, but later discovered that their proof was not correct (personal communication with S. Kamali)..

To address this open problem, we develop an online algorithm Full-Or-Partial-Move (Fpm) for ${\text{LUP}}_1$ with competitive ratio $\frac{1}{8}\cdot (23+\sqrt{17})\approx 3.3904$, significantly improving the previous upper bound of $4$.

Our algorithm Fpm remains $3.3904$-competitive even for the partial cost function, where the cost of accessing location $\mathrm{\ell }$ is $\mathrm{\ell }-1$, instead of the full cost of $\mathrm{\ell }$ used in the original definition of List Update [25]. Both functions have been used in the literature, depending on context and convenience. For any online algorithm, its partial-cost competitive ratio is at least as large as its full-cost ratio, although the difference typically vanishes when the list size is unbounded. We present our analysis in terms of partial costs.

Fpm remains $3.3904$-competitive also in the dynamic scenario of List Update that allows operations of insertions and deletions, as in the original definition in [25] (see the full version of the paper [14]).

The question whether ratio $3$ can be achieved remains open. We also do not know if there is a simple algorithm with ratio below $4$. We have considered some natural adaptions of Mtf and other algorithms that are $2$-competitive for ${\text{LUP}}_{\mathrm{S}}$, but for all we were able to show lower bounds higher than $3$ for ${\text{LUP}}_1$.

As earlier mentioned, Mtf is $4$-competitive for ${\text{LUP}}_1$. It is also easy to show that its ratio is not better than $4$: repeatedly request the last item in the list. Ignoring additive constants, the algorithm pays twice the length of the list at each step, while any algorithm that just keeps the list in a fixed order, pays only half the length on the average.

The intuition why Mtf performs poorly is that it moves the requested items to front “too quickly”. For the aforementioned adversarial strategy against Mtf, ratio $3$ can be obtained by moving the items to front only every other time they are requested. This algorithm, called Dbit, is a deterministic variant of algorithm Bit from [24] and a special case of algorithm Counter in [24], and it has been also considered in [21]. In the full version of the paper [14], we show that Dbit is not better than $4$-competitive in the partial cost model, and not better than $3.302$-competitive in the full cost model.

One can generalize these approaches by considering a more general class of algorithms that either leave the requested item at its current location or move it to the front. We show that such a strategy cannot achieve ratio better than $3.25$, even for just three items. A naive fix would be, for example, to always move the requested item half-way towards front. This algorithm is even worse: its competitive ratio is at least $6$ (both those proofs are in the full version of the paper [14]).

We also show (see Section 5) via a computer-aided argument that, for ${\text{LUP}}_1$, the work function algorithm’s competitive ratio is larger than $3$, even for lists of length $5$. This is in contrast to the its performance for the standard model, where it achieves optimal ratio $2$ [9].

Our algorithm Fpm overcomes the difficulties mentioned above by combining a few new ideas. The first idea is a more sophisticated choice of the target location for the requested item. That is, aside from full moves that move the requested items to the list front, Fpm sometimes performs a partial move to a suitably chosen target location in the list. This location roughly corresponds to the front of the list when this item was requested earlier.

The second idea is to keep track, for each pair of items, of the work function for the two-item subsequence consisting of these items. These work functions are used in two ways. First, they roughly indicate which relative order between the items in each pair is “more likely” in an optimal solution. The algorithm uses this information to decide whether to perform a full move or a partial move. Second, the simple sum of all these pair-based work functions is a lower bound on the optimal cost, which is useful in analyzing the competitive ratio of Fpm.

Better bounds are known for randomized algorithms both in the standard model (${\text{LUP}}_{\mathrm{S}}$) and the uniform cost model (${\text{LUP}}_1$). For ${\text{LUP}}_{\mathrm{S}}$, a long line of research culminated in a $1.6$-competitive algorithm [19, 24, 2, 6], and a $1.5$-lower bound [26]. The upper bound of $1.6$ is tight in the class of so-called projective algorithms, whose computation is uniquely determined by their behavior on two-item instances [8]. For ${\text{LUP}}_1$, the ratio is known to be between $1.5$ [4] and $2.64$ [24].

It is possible to generalize the uniform cost function by distinguishing between the cost of $1$ for following a link during search and the cost of $d\ge 1$ for a swap [24, 4] This model is sometimes called the $P^d$ model; in this terminology, our ${\text{LUP}}_1$ corresponds to $P^1$. While Mtf is $4$-competitive for $P^1$, it does not generalize in an obvious way to $d>1$. Other known algorithms for the $P^d$ model (randomized and deterministic Counter, RandomReset and TimeStamp) have bounds on competitive ratios that monotonically decrease with growing $d$ [24, 4]. In particular, deterministic Counter achieves ratio $4.56$ when $d$ tends to infinity [7] and for the same setting ($d\to \mathrm{\infty }$) a recent result by Albers and Janke [4] shows a randomized algorithm TimeStamp that is $2.24$-competitive.

A variety of List Update variants have been investigated in the literature over the last forty years, including models with lookahead [1], locality of reference [10, 5], parameterized approach [17], algorithms with advice [16], prediction [11], or alternative cost models [18, 22, 23]. A particularly interesting model was proposed recently by Azar et al.  [12], where an online algorithm is allowed to postpone serving some requests, but is either required to serve them by a specified deadline or pay a delay penalty.

In summary, List Update is one of canonical problems in the area of competitive analysis, used to experiment with refined models of competitive analysis or to study the effects of additional features. This underscores the need to fully resolve the remaining open questions regarding its basic variants, including the question whether ratio $3$ is attainable for ${\text{LUP}}_1$.

An algorithm has to maintain a list of items, while a sequence $\sigma$ of access requests is presented in an online manner. In each step $t\ge 1$, the algorithm is presented an access request ${\sigma }^t$ to an item in the list. If this item is in a location $\mathrm{\ell }$, the algorithm incurs cost $\mathrm{\ell }-1$ to access it. (The locations in the list are indexed $1,2,\mathrm{\dots }$.) Afterwards, the algorithm may change the list configuration by performing an arbitrary number of swaps of neighboring items, each of cost $1$.

For any algorithm $A$, we denote its cost for processing a sequence $\sigma$ by $A(\sigma )$. The optimal algorithm is denoted by Opt.

Let $𝒫$ be the set of all unordered pairs of items. For a pair $\{x,y\}\in 𝒫$, we use the notation $x\prec y$ ($x\succ y$) to denote that $x$ is before (after) $y$ in the list of an online algorithm. (The relative order of $x,y$ may change over time, but it will be always clear from context what step of the computation we are referring to.) We use $x⪯y$ ($x⪰y$) to denote that $x\prec y$ ($x\succ y$) or $x=y$.

For an input $\sigma$ and a pair $\{x,y\}\in 𝒫$, ${\sigma }_{xy}$ is the subsequence of $\sigma$ restricted to requests to items $x$ and $y$ only. Whenever we say that an algorithm serves input ${\sigma }_{xy}$, we mean that it has to maintain a list of two items, $x$ and $y$.

Whenever an item $z^{\ast }$ is requested, Fpm performs the following three operations, in this order:

1. Target cleanup. If $z^{\ast }$ was a target of another item $y$ (i.e., ${\theta }_y=z^{\ast }$ for $y\ne z^{\ast }$), then ${\theta }_y$ is updated to the successor of $z^{\ast }$. This happens for all items $y$ with this property.

2. Movement of $z^{\ast }$. Fpm executes one of the two actions: a partial move or a full move. We will explain how to choose between them later.

• $\mathrm{■}$

  In the partial move, item $z^{\ast }$ is inserted right before ${\theta }_{z^{\ast }}$. (If ${\theta }_{z^{\ast }}=z^{\ast }$, this means that $z^{\ast }$ does not change its position.)

• $\mathrm{■}$

  In the full move, item $z^{\ast }$ is moved to the front of the list.

3. Target reset. ${\theta }_{z^{\ast }}$ is set to the front item of the list.

It is illustrative to note a few properties and corner cases of the algorithm.

• $\mathrm{■}$

  Target cleanup is executed only for items following $z^{\ast }$, and thus the successor of $z^{\ast }$ exists then (i.e., Fpm is well defined).

• $\mathrm{■}$

  If ${\theta }_{z^{\ast }}=z^{\ast }$ and a partial move is executed, then $z^{\ast }$ is not moved, but the items that targeted $z^{\ast }$ now target the successor of $z^{\ast }$.

• $\mathrm{■}$

  For an item $x$, the items that precede ${\theta }_x$ in the list were requested (each at least once) after the last time $x$ had been requested.

Fix a pair $\{x,y\}$ such that $y\prec x$, and thus also ${\theta }_y⪯y\prec x$. This pair is assigned one of four possible flavors, depending on the position of ${\theta }_x$ (cf. Figure 2):

• $\mathrm{■}$

  flavor $d$ (disjoint): if ${\theta }_y⪯y\prec {\theta }_x⪯x$,

• $\mathrm{■}$

  flavor $o$ (overlapping): if ${\theta }_y\prec {\theta }_x⪯y\prec x$,

• $\mathrm{■}$

  flavor $e$ (equal): if ${\theta }_y={\theta }_x⪯y\prec x$,

• $\mathrm{■}$

  flavor $n$ (nested): if ${\theta }_x\prec {\theta }_y⪯y\prec x$

For a pair $\{x,y\}$ that is in a mode $\xi \in \{\alpha ,\beta ,\gamma \}$ and has a flavor $\omega \in \{d,o,e,n\}$, we say that the state of $\{x,y\}$ is ${\xi }^{\omega }$. Recall that all pairs are initially in mode $\alpha$, and note that their initial flavor is $d$. That is, the initial state of all pairs is ${\alpha }^d$.

We will sometimes combine the flavors $o$ with $e$, stating that the pair is in state ${\xi }^{oe}$ if its mode is $\xi$ and its flavor is $o$ or $e$. Similarly, we will also combine flavors $n$ and $e$.

To each pair $\{x,y\}$ of items, we assign a non-negative pair potential ${\mathrm{\Phi }}_{xy}$. We abuse the notation and use ${\xi }^{\omega }$ not only to denote the pair state, but also the corresponding values of the pair potential. That is, we assign the potential ${\mathrm{\Phi }}_{xy}={\xi }^{\omega }$ if pair $\{x,y\}$ is in state ${\xi }^{\omega }$. We pick the actual values of these potentials only later in Subsection 4.5.

We emphasize that the states of each item pair depend on work functions for this pair that are easily computable in online manner. Thus, Fpm may compute the current values of ${\mathrm{\Phi }}_{xy}$, and also compute how their values would change for particular choice of a move.

For a step $t$, let ${\mathrm{\Delta }}_t\text{Fpm}$ be the cost of Fpm in this step, and for a pair $\{x,y\}\in 𝒫$, let ${\mathrm{\Delta }}_t{\mathrm{\Phi }}_{xy}$ be the change of the potential of pair $\{x,y\}$ in step $t$. Let $z^{\ast }$ denote the requested item. Fpm chooses the move (full or partial) with the smaller value of

breaking ties arbitrarily. Importantly, note that the value that Fpm minimizes involves only pairs including the requested item $z^{\ast }$ and items currently preceding it.