# Learning Minimum Linear Arrangement
of Cliques and Lines††thanks: This paper has been supported by Polish National
Science Centre grant 2022/45/B/ST6/00559 and the Austrian Science Fund (FWF)
project I 5025-N (DELTA). For the purpose of Open Access, the authors have
applied CC-BY public copyright license to any Author Accepted Manuscript (AAM)
version arising from this submission.

Julien Dallot  Technische Universität Berlin, Germany  Maciej Pacut
Technische Universität Berlin, Germany  Marcin Bienkowski  University of
Wroclaw, Poland  Darya Melnyk  Technische Universität Berlin, Germany  Stefan
Schmid  Technische Universität Berlin, Germany

###### Abstract

In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to
arrange the nodes of an undirected graph into a permutation so that the total
stretch of the edges is minimized. This paper studies an online (learning)
variant of MinLA where the graph is not given at the beginning, but rather
revealed piece-by-piece. The algorithm starts in a fixed initial permutation,
and after a piece of the graph is revealed, the algorithm must update its
current permutation to be a MinLA of the subgraph revealed so far. The
objective is to minimize the total number of swaps of adjacent nodes as the
algorithm updates the permutation.

The main result of this paper is an online randomized algorithm that solves
this online variant for the restricted cases where the revealed graph is
either a collection of cliques or a collection of lines. We show that the
algorithm is $8\ln n$-competitive, where $n$ is the number of nodes of the
graph. We complement this result by constructing an asymptotically matching
lower bound of $\Omega(\ln n)$.

##  1 Introduction

Minimum Linear Arrangement (MinLA) [29, 34, 23, 23, 27] is a classic
combinatorial optimization problem that arises in the field of graph theory
and network design. The objective is to arrange the nodes of an undirected
graph along a straight line in such a way that the sum of the distances
between adjacent nodes is minimized. The problem finds applications in various
domains, including VLSI circuit design, transportation network planning, and
communication network layout [19, 6, 4]. The problem is formally defined as
follows. Let $G=(V,E)$ be a graph with $n$ nodes and $m$ edges. The goal of
the MinLA problem is to find a permutation $\pi$ of the nodes of $G$ so that
the total distance between the edges is minimized. Formally, it amounts to
finding $\pi\in S_{n}$ such that the quantity

$\displaystyle\sum\limits_{(x,y)\in E}|\pi(x)-\pi(y)|$

is minimized, where $\pi(x)$ denotes the position of node $x$ in the
permutation $\pi$.

In this paper, we study the online _learning_ variant of the MinLA problem. In
the online learning variant, the graph is not given right away but rather
revealed piece-by-piece in a potentially adversarial order. We call
$G_{0},G_{1},\dots G_{k}$ the sequence of the revealed graphs, where $G_{0}$
is the empty graph, each $G_{i}$ is a super-graph of its predecessors, and
$G_{k}=G$. The online algorithm starts with a given initial permutation
$\pi_{0}$ and, upon receiving graph $G_{i}$, it _must_ update its current
permutation $\pi_{i-1}$, so that _the new permutation $\pi_{i}$ is a MinLA of
$G_{i}$_. The goal of the online MinLA problem is to find a sequence of
permutations $\pi_{0},\dots,\pi_{k}$, such that the total cost of the
permutation updates is minimized. More formally, the algorithm must minimize
the quantity

$\displaystyle\sum\limits_{i=0}^{k-1}d(\pi_{i},\pi_{i+1}),$

where $d$ is the cost to update a permutation. We choose $d$ to be Kendall’s
$\tau$ distance, that is, the minimum number of pairwise swaps of adjacent
elements required to change one permutation into the other.

We use the notion of competitive ratio to assess the performance of our online
algorithms [9]. For a given request sequence $\sigma$, let
$\textsc{Onl}(\sigma)$ and $\textsc{Opt}(\sigma)$ be the cost incurred by an
online algorithm Onl and an optimal offline algorithm Opt, respectively. In
contrast to Onl, Opt knows the entire request sequence $\sigma$ ahead of time.
The goal is to design online algorithms for online learning MinLA that provide
worst-case guarantees. In particular, Onl is said to be $c$-competitive if for
any input sequence $\sigma$ it holds that $\textsc{Onl}(\sigma)\leq
c\cdot\textsc{Opt}(\sigma)$.

This work aligns with a broader line of work that searches for efficient
online algorithms for classic offline optimization problems. As dealing with
an unknown future is a ubiquitous scenario, there exists an extensive
literature on online variants of well-known problems, including set cover [1,
10], graph matching [22, 17], graph coloring [35, 14], load balancing [28],
maximum independent set [18], and bin packing [33, 5]. So far, the MinLA
problem has received considerable attention in the offline setting [34, 23,
13, 27] either due to its many application cases [19, 6, 4] or its theoretical
importance [2, 15], and developing a competitive online algorithm is a natural
step in this line of research.

Our work is related the closest to work of Olver et al. [25], who introduced
the _dynamic_ MinLA problem and its variants (such as the itinerant list
update problem). Their setting is less restricted than ours and it leaves more
freedom on how to serve a request: when an edge is revealed in their variant,
an algorithm simply pays the distance between its endpoints in its current
permutation, and then may optionally rearrange the nodes to save cost on
future requests, the goal being to minimize the total incurred cost. In
particular, in their dynamic setting an algorithm does not have to maintain a
MinLA of the graph induced by edges seen so far while our setting is learning
the graph and remembers previous edges.

Their problem received the most attention in its offline setting: Olver et al.
[25] presented a randomized $(\log^{2}n)$-approximation algorithm, later
improved by Bienkowski and Even to a deterministic algorithm with a $(\log
n\log\log n)$-approximation [8]. While the online variant of the dynamic MinLA
problem is regularly mentioned [25, 8], no advances were made on this front;
the only results so far were a lower bound of $\Omega(\log n)$ for the
competitive ratio of any randomized online algorithm [25], and a trivial upper
bound of $O(n)$ held by the algorithm that never changes its permutation.

To the best of our knowledge, this paper hence is the first to tackle a
variant of the problem in the online setting hopefully paving the way towards
more general results for the online dynamic MinLA problem.

###  1.1 Contributions

We consider online learning MinLA problem in a restricted case where each
graph $G_{i}$ in the input is either a collection of disjoint cliques or a
collection of disjoint lines (paths). This restriction captures fundamental
questions that arise in a general setting: (1) where to move the two disjoint
components that have just been connected by revealing of a new piece of the
graph, and (2) which orientation should the connected component have in the
permutation.

We develop two online algorithms for this setting: a deterministic one and a
randomized one. We begin with the deterministic online algorithm, prove it is
$2n$-competitive and show that the analysis is tight. The main contribution of
this paper, however, is the randomized online algorithm that is $8\ln
n$-competitive against the oblivious adversary [9]. Finally, we show a
randomized lower bound of $\Omega(\log n)$, proving that our algorithm is
asymptotically optimal.

###  1.2 Motivation: Dynamic Virtual Network Embedding

With the increasing popularity of data-centric workloads, such as distributed
machine learning and scale-out databases, datacenters are witnessing a
significant surge in network traffic [32]. The performance of these
distributed applications heavily relies on the efficiency of the underlying
communication networks [24].

An intriguing approach to improve the efficiency of communication networks is
to adjust the network in a demand-aware and online manner. This can be done by
leveraging resource allocation flexibilities provided by virtualization. When
communication requests arrive over time, algorithms can decide to move
frequently communicating nodes topologically closer. Since relocation comes at
a cost, the task is to strike a balance between the benefits and the costs of
the adjustments. The underlying optimization problem involves dynamically
embedding a virtual network on a physical network topology.

The basic virtual network embedding problem of finding a mapping from a
request graph to the virtual network is well-studied [16, 30, 11, 12, 31], and
many problem variants have been shown to be $\mathcal{NP}$-complete [16, 30,
11]. One of the most studied problems in graph embedding is the minimum linear
arrangement problem. This problem is $\mathcal{NP}$-hard in general,
therefore, significant efforts have been made to solve it for restricted guest
graphs such as trees [34] or incomplete hypercubes [23].

The problem variant of _dynamically_ embedding a virtual network on a physical
network topology is, however, more challenging. So far, the dynamic problem
has been considered for two fundamental physical network topologies: (1) a set
of capacitated clusters connected in a clique and (2) the line topology. In
the first setting, the problem is known as the _online graph partitioning_
problem [3, 21, 20, 26], and in the latter setting, it is known as the
_dynamic minimum linear arrangement_ problem (a.k.a. itinerant list update
problem [25]).

The online learning MinLA model is inspired by the learning variant of online
graph partitioning, introduced at SIGMETRICS 2019 [21], with followup work at
INFOCOM 2020 [26] and SODA 2021 [20]. The goal is to learn and embed the
communication pattern (the guest graph) over time in an online manner.

We develop an _optimally competitive_ randomized online algorithms for online
learning MinLA for two fundamental traffic patterns: collection of lines and
collection of cliques. These topologies represent the most sparse and most
dense traffic patterns and are an important stepping stone toward more complex
network topologies.

###  1.3 Related Work

The model introduced in this paper is related to two online problems: _online
graph partitioning_ , introduced at DISC 2016 [3], and _dynamic minimum linear
arrangement_ , introduced at WAOA 2018 [25].

In the online graph partitioning problem [3], a network topology connecting
$\ell$ clusters each containing $k$ virtual nodes is considered. The requests
concern pairs of nodes, and if the requested nodes are collocated within a
single cluster, the request costs $0$, and otherwise, it costs $1$. For this
problem, the best known competitive ratio is $(k\cdot\ell\cdot
2^{O(k)})$-competitive [7], and no deterministic algorithm can be better than
$\Omega(k\cdot\ell)$-competitive [26]. Significant research efforts on the
graph partitioning problem have focused on the learning variant [21, 26, 20].

In the dynamic minimum linear arrangement problem [25], the underlying
topology is a line and the requests are pairs of virtual nodes. The cost for
serving a request is proportional to the distance between the corresponding
virtual nodes, but collocation is not strictly enforced. A $(\log
n\cdot\log\log n)$-approximation algorithm for this problem has been derived
in the offline setting, where all the requests are known in advance [25, 8].
The paper of [25] shows a randomized lower-bound of $\Omega(\log n)$ for the
dynamic MinLA problem in the online setting. So far, the only general upper
bound is a trivial $O(n)$ bound, which can be achieved even by an algorithm
that never migrates (however we point out that in the model studied in this
paper, applying this algorithm is not viable). A simple online algorithm that
moves the smaller component towards the larger has an upper bound of
$O(n^{2}\cdot\log n)$ on the total incurred cost [4], but under strict
competitive analysis this algorithm is $\Omega(n)$-competitive, and neither
the algorithm nor the analysis translates to our setting.

###  1.4 Organization

This manuscript is organized as follows. In Section 2, we design and analyze a
simple deterministic algorithm that attains a linear competitive ratio for the
case of embedding a collection of lines or a collection of cliques. In Section
3, we design a randomized algorithm attaining a logarithmic competitive ratio
for the case of embedding a collection of cliques. In Section 4, we adapt the
previous algorithm to attain a logarithmic competitive ratio for the case of
embedding a collection of lines. In Section 5, we prove the tightness of these
algorithms. We conclude in Section 6.

##  2 A Deterministic Algorithm

In this section, we present a simple $O(n)$-competitive deterministic
algorithm Det for solving online MinLA for both cases where the subgraphs
$G_{i}$ either are collections of cliques or collection of lines. In Section 5
we show that the analysis of Det algorithm is tight for both graph classes.
This algorithm is an adaptation of an algorithm Perfect Partition Learner for
the _online graph partitioning problem_ [26].

The algorithm Det is defined as follows. Upon each request $G_{i}$, Det
updates the permutation to an arbitrary MinLA of $G_{i}$ that minimizes the
distance to $\pi_{0}$.

In the rest of this section, we argue that the competitive ratio of this
algorithm is linear in terms of the number of nodes.

######  Theorem 1.

Det is $(2n-2)$-competitive for the case where the graph is either a
collection of lines or a collection of cliques.

###### Proof.

Fix a request sequence $G_{0},G_{1},\dots G_{k}$, an initial permutation
$\pi_{0}$ and an optimal offline algorithm Opt with final permutation
$\pi_{k}^{\textsc{Opt}}$. We denote $d(\pi_{0},\pi_{k}^{\textsc{Opt}})$ by
$\Delta^{*}$.

First, we claim that for any permutation $\pi_{i}$ reached by Det throughout
its execution, we have $d(\pi_{0},\pi_{i})\leq\Delta^{*}$. Notice that,
whether the subgraphs are collections of cliques or collections of lines, a
permutation that is a MinLA of $G_{k}$ is always also a MinLA of any $G_{i}$
for $i\leq k$. As a result, Det considers $\pi_{k}^{\textsc{Opt}}$ as a
potential next permutation each time a new subgraph is revealed. Since Det
picks the permutation that minimizes its distance from $\pi_{0}$, we directly
derive that $d(\pi_{0},\pi_{i})\leq\Delta^{*}$.

Second, we claim that the cost of serving each request by Det is at most
$2\cdot\Delta^{*}$. We argue as follows. Consider an update from a permutation
$\pi_{i-1}$ to $\pi_{i}$. In the previous paragraph, we argued that both these
permutations are no further than $\Delta^{*}$ away from $\pi_{0}$. Using the
triangle inequality we have that $d(\pi_{i-1},\pi_{i})\leq
d(\pi_{i-1},\pi_{0})+d(\pi_{0},\pi_{i})\leq 2\cdot\Delta^{*}$.

Finally, we bound the competitive ratio. We have that $\textsc{Opt}\geq
d(\pi_{0},\pi_{k}^{\textsc{Opt}})=\Delta^{*}$, as both Opt and Det start in
the same permutation. The sequence of subgraphs $G_{1},\dots G_{k}$ has length
at most $n-1$. In the previous paragraph, we argued that each request costs at
most $2\cdot\Delta^{*}$, hence the total cost of Det is at most
$2(n-1)\cdot\Delta^{*}$. Hence, $\textsc{Det}/\textsc{Opt}\leq
2(n-1)\cdot\Delta^{*}/\Delta^{*}=2(n-1)$. ∎

In Section 5, we show that our analysis of Det algorithm is tight.

##  3 An Optimal Randomized Algorithm for Cliques

###  3.1 Description of the Algorithm

In this section, we present a randomized algorithm Rand for the MinLA problem
when the subgraphs $G_{0},\dots G_{k}$ all are collections of cliques. We will
prove that this algorithm holds an expected competitive ratio of $4\ln n$
against the oblivious adversary [9].

Let $X_{i}$ and $Z_{i}$ be the nodes of the two components (cliques) that
merge between $G_{i}$ and $G_{i+1}$. In response to the reveal of $G_{i+1}$,
Rand handles the necessary update by placing $X_{i}$ and $Z_{i}$ next to each
other in $\pi_{i+1}$. Rand only considers two of the potentially many possible
permutations where $X_{i}$ and $Z_{i}$ end up next to each other: starting
from $\pi_{i}$, either the nodes of $X_{i}$ move in direction of $Z_{i}$ or
conversely, the nodes of $Z_{i}$ move in direction of $X_{i}$.

Our algorithm chooses between those two choices by flipping a biased coin:
$X_{i}$ moves with probability $|Z_{i}|/(|X_{i}|+|Z_{i}|)$ and $Z_{i}$ moves
with probability $|X_{i}|/(|X_{i}|+|Z_{i}|)$. Figure 1 summarizes the possible
actions of our algorithm.

$\cdots$$X_{i}$$Z_{i}$$\cdots$$X_{i}$$Z_{i}$$\cdots$$X_{i}$$Z_{i}$$\begin{subarray}{c}\text{Move
}Z_{i}\text{ with}\\\ \text{probability
}\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}\end{subarray}$$\begin{subarray}{c}\text{Move
}X_{i}\text{ with}\\\ \text{probability
}\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}\end{subarray}$ Figure 1: The two possible
actions of Rand to move the merging components $X_{i}$ and $Z_{i}$ together
when $G_{i+1}$ is revealed

In the rest of this section, we will prove the following theorem.

######  Theorem 2.

The algorithm Rand is $4\ln n$-competitive for online MinLA when all the
revealed subgraphs are collections of cliques.

To prove the theorem, we first introduce necessary notation.

###  3.2 Notation

Let $\mathcal{C}_{i}$ be the set of components of $G_{i}$, a component is the
set of nodes of a connected component. We call $X_{i},Z_{i}\in\mathcal{C}_{i}$
the two components that merge into a bigger clique when $G_{i+1}$ is revealed.

For $i\in\\{0\dots k\\}$, let $T,U\in\mathcal{C}_{i}$ be two components. For
these, we define:

  * •

$T\times U=\left\\{(t,u)|t\in T,u\in U\right\\}$ is the Cartesian product of
$T$ and $U$.

  * •

$T\textrm{---}U$ is the event that $T$ is on the left of $U$;
$P[T\textrm{---}U]$ is the associated probability that Rand is in a
configuration with such order between the components.

  * •

$L_{\pi_{i}}$ is the set of all node pairs $(x,y)$ such that $x$ is on the
left of $y$ in $\pi_{i}$.

  * •

$L_{T,U}$ is the set of all pairs that contain exactly one node from $T$ and
one node from $U$ in any order, i.e., $L_{T,U}=T\times U\cup U\times T$.

Notice that the event $T\textrm{---}U$ is not indexed by $i$. This is because,
by the properties of our algorithm, the relative position of two components
$T$ and $U$ can change only if a node of $T$ or $U$ is requested; but if this
happens then the requested component stops being a component (it becomes a
part of a bigger one) and the event $T\textrm{---}U$ has no more meaning.
Hence any two components will have only one relative position (if they happen
to exist at the same moment) and the event $T\textrm{---}U$ is independent
from $i$.

###  3.3 Upper Bound on the Expected Cost

We start the analysis with a lemma that gives the probability ruling the
relative position of any two components throughout the execution of Rand.

######  Lemma 3.

Let $i\in\\{0\dots k\\}$, let $X$ and $Y$ be two components of
$\mathcal{C}_{i}$. It holds that

$\displaystyle P[X\textrm{---}Y]=\frac{|X\times Y\cap
L_{\pi_{0}}|}{|X|\cdot|Y|}.$

###### Proof.

We prove the claim by induction on $i$. If $i=0$ then nothing was revealed so
far, the components are the nodes themselves and the claim holds.

Let $i\in\\{1\dots k\\}$, we assume that the claim holds for all components
when $G_{i}$ is revealed. We then prove that the claim also holds after
$G_{i+1}$ was revealed. Let $Y$ be a component different from the merging
components $X_{i}$ and $Z_{i}$. We compute the probability that $(X_{i}\cup
Z_{i})\textrm{---}Y$, i.e., that the newly formed component $X_{i}\cup Z_{i}$
is on the left of $Y$ after $X_{i}$ merged with $Z_{i}$.

$\displaystyle P[(X_{i}\cup Z_{i})\textrm{---}Y]$
$\displaystyle=P[X_{i}\textrm{---}Y]\cdot
P[Z_{i}\textrm{---}Y]+P[X_{i}\textrm{---}Y]\cdot
P[Y\textrm{---}Z_{i}]\cdot\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}$
$\displaystyle\quad\quad+P[Z_{i}\textrm{---}Y]\cdot
P[Y\textrm{---}X_{i}]\cdot\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}$
$\displaystyle=P[X_{i}\textrm{---}Y]\cdot\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}+P[Z_{i}\textrm{---}Y]\cdot\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}$
$\displaystyle=\frac{|(X_{i}\cup Z_{i})\times Y\cap L_{\pi_{0}}|}{|X_{i}\cup
Z_{i}|\cdot|Y|}.$

We applied the induction hypothesis to obtain the final result. By symmetry,
we have the same results for computing $P[Y\textrm{---}(X_{i}\cup Z_{i})]$.
The induction holds and the claim follows. ∎

Lemma 3 implies that, at any moment, the probabilistic relative position of
any two components of Rand’s permutation only depends on the initial
permutation after $G_{i}$ was revealed. In particular, the probability
distribution of the permutation $\pi_{i}$ is independent on the reveal order.

We now use this lemma to upper-bound the cost of an update. For any set of
nodes $U$ and $T$, we call $M_{U,T}^{i}$ the total number of swaps that occurs
between a node of $U$ and a node of $T$ as Rand updates its permutation from
$\pi_{i}$ to $\pi_{i+1}$.

######  Lemma 4.

Let $0\leq i\leq k-1$, let $Y\in\mathcal{C}_{i}$ different from the merging
components $X_{i}$ and $Z_{i}$. It holds that

$\displaystyle\frac{1}{2}\mathbb{E}[M_{Y,X_{i}\cup Z_{i}}^{i}]$
$\displaystyle\leq|(L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{X_{i},Y}|\cdot\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}$
$\displaystyle\quad\quad+|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{Z_{i},Y}|\cdot\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}.$

###### Proof.

The nodes of $Y$ will swap with nodes of $X_{i}$ or $Z_{i}$ if and only if $Y$
is between $X_{i}$ and $Z_{i}$ when $G_{i+1}$ is revealed. Expressed in the
terms of Lemma 3 this condition becomes: the nodes of $Y$ will swap with those
of $X_{i}$ or $Z_{i}$ only if $X_{i}$ is on the left of $Y$ and $Z_{i}$ on the
right, or conversely.

Multiplying the expected cost in case $Y$ crosses one of the merging
components by the probability that $Y$ is between $X_{i}$ and $Z_{i}$, we
obtain that

$\mathbb{E}[M_{Y,X_{i}\cup
Z_{i}}^{i}]=2|Y|\frac{|Z_{i}|\cdot|X_{i}|}{|X_{i}|+|Z_{i}|}\cdot\left(P[X_{i}\textrm{---}Y]\cdot
P[Y\textrm{---}Z_{i}]+P[Z_{i}\textrm{---}Y]\cdot
P[Y\textrm{---}X_{i}]\right).$

In $\pi_{k}^{\textsc{Opt}}$, the nodes from $X_{i}\cup Z_{i}$ occupy
contiguous places. Hence, $Y$ is either on the right or on the left of
$X_{i}\cup Z_{i}$ in $\pi_{k}^{\textsc{Opt}}$; using the problem’s symmetries
we assume that $Y$ is on the left of $X_{i}\cup Z_{i}$ in
$\pi_{k}^{\textsc{Opt}}$ without loss of generality. We now upper-bound the
probabilities $P[Y\textrm{---}X_{i}]$ and $P[Y\textrm{---}Z_{i}]$ in the last
equation by $1$ and apply Lemma 3:

$\displaystyle\frac{1}{2}\mathbb{E}[M_{Y,X_{i}\cup Z_{i}}^{i}]$
$\displaystyle\leq|Y|\cdot\frac{|Z_{i}|\cdot|X_{i}|}{|X_{i}|+|Z_{i}|}\cdot\left(P[X_{i}-Y]+P[Z_{i}-Y]\right)$
$\displaystyle=|X_{i}\times Y\cap
L_{\pi_{0}}|\cdot\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}+|Z_{i}\times Y\cap
L_{\pi_{0}}|\cdot\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}.$

All node pairs in $X_{i}\times Y\cap L_{\pi_{0}}$ have a node from $X_{i}$ on
the left and a node from $Y$ on the right. Likewise, all pairs in $Z_{i}\times
Y\cap L_{\pi_{0}}$ have a node from $Z_{i}$ on the left part and a node from
$Y$ on the right part. Hence, neither of those two sets share a pair with
$Y\times X_{i}$, $Y\times Z_{i}$ or $\pi_{k}^{\textsc{Opt}}$. As a result, it
holds that

$\displaystyle|X_{i}\times Y\cap L_{\pi_{0}}|=|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap L_{X_{i},Y}|$

and

$\displaystyle|Z_{i}\times Y\cap L_{\pi_{0}}|=|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap L_{Z_{i},Y}|,$

which ends the proof. ∎

We state an auxiliary lemma before stating the final theorem.

######  Lemma 5.

Let $s_{1},s_{2},\dots s_{N}$ be a series of strictly positive natural
numbers, let $S=\sum_{i=1}^{N}s_{i}$ be their sum. It holds that

$\displaystyle\sum_{i=1}^{N}\frac{s_{i}}{\sum_{j=1}^{i}s_{j}}\leq H_{S}.$

where $H_{S}=1+\frac{1}{2}+\dots+\frac{1}{S}$ is the harmonic sum.

###### Proof.

$\sum_{i=1}^{N}\frac{s_{i}}{\sum_{j=1}^{i}s_{j}}=\sum_{i=1}^{N}\sum_{k=1}^{s_{i}}\frac{1}{\sum_{j=1}^{i}s_{j}}\leq\sum_{i=1}^{N}\sum_{k=1}^{s_{i}}\frac{1}{\sum_{j=1}^{i-1}s_{j}+k}=\sum_{i=1}^{S}\frac{1}{i}.\qed$

######  Theorem 6.

Let $M$ be the random variable equal to the cost of Rand. Then,
$\mathbb{E}[M]\leq 4H_{n}\cdot|L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}|$, where $H_{n}$ is the harmonic sum.

###### Proof of Theorem 6.

We use Lemma 4 to upper-bound $M$. It holds that

$\displaystyle\frac{1}{2}\mathbb{E}[M]$
$\displaystyle=\sum\limits_{i=0}^{k-1}\sum\limits_{\begin{subarray}{c}Y\in\\\
\mathcal{C}_{i}\setminus\\{X_{i},Z_{i}\\}\end{subarray}}\frac{1}{2}\mathbb{E}[M_{Y,X_{i}\cup
Z_{i}}^{i}]$
$\displaystyle\leq\sum\limits_{i=0}^{k-1}\sum\limits_{\begin{subarray}{c}Y\in\\\
\mathcal{C}_{i}\setminus\\{X_{i},Z_{i}\\}\end{subarray}}\left(|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{X_{i},Y}|\cdot\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}+|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{Z_{i},Y}|\cdot\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}\right)$
$\displaystyle=\sum\limits_{i=0}^{k-1}\left(|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap L_{X_{i},V\setminus
X_{i}}|\cdot\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}+|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap L_{Z_{i},V\setminus
Z_{i}}|\cdot\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}\right).$

We now rewrite the above sum in terms of pairs rather than edges:

$\frac{1}{2}\mathbb{E}[M]\leq\sum\limits_{p\in L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}}\sum\limits_{i=0}^{k-1}\left(\frac{|Z_{i}|}{|X_{i}|+|Z_{i}|}\cdot\mathbbm{1}(p\in
L_{X_{i},V\setminus
X_{i}})+\frac{|X_{i}|}{|X_{i}|+|Z_{i}|}\cdot\mathbbm{1}(p\in
L_{Z_{i},V\setminus Z_{i}})\right).$ (1)

Let $p$ be a pair in $L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}}$. $p$
has a strictly positive coefficient for $i$ in the above sum if and only if
$p$ has one of its nodes contained in $X_{i}$ or $Z_{i}$. As a result, for
each $i$ so that $p$ has a strictly positive coefficient in the sum, one of
the components that contains a node of $p$ merges into a bigger one in the
next graph $G_{i+1}$.

Let $y$ be a node in $p$, let $Y_{1}\dots Y_{N}$ be the components that
successively merge with $y$’s component — we call $Y_{0}$ the initial
component containing only $y$. Summing all the coefficients corresponding to
pair $p$ and where $y$ is in a merging component gives

$\sum\limits_{i=1}^{N}\frac{|Y_{i}|}{\sum_{j=0}^{i}|Y_{j}|},$

which is lower than $H_{n}$ using Lemma 5. There is such a sum for the two
nodes of every pair $p\in L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}}$ in
inequality (1). Hence the claim holds. ∎

######  Observation 7.

Let Opt be an optimal offline algorithm and let $\pi_{k}^{\textsc{Opt}}$ be
its final permutation. Then, $c(\textsc{Opt})\geq|L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}|$.

###### Proof.

The claim directly follows from the fact that
$d(\pi_{0},\pi_{k}^{\textsc{Opt}})=|L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}|$. ∎

Combining Theorem 6 and Observation 7 and using the well-known relationships
between the harmonic sum and the natural logarithm finally proves Theorem 2.

##  4 An Optimal Randomized Algorithm for Lines

###  4.1 Description of the Algorithm

In this section, we present a randomized algorithm Rand for the MinLA problem
when the subgraphs $G_{0},G_{1},\dots G_{k}$ are collections of lines. We will
prove that this algorithm holds an expected competitive ratio of $8\ln n$
against the oblivious adversary [9].

Let $x_{i}$ and $z_{i}$ be the endpoints of the edge that is revealed between
$G_{i}$ and $G_{i+1}$. We call $X_{i}$ and $Z_{i}$ the components that contain
$x_{i}$ and $z_{i}$ — a component refers to the nodes of a connected
component. In response to $G_{i+1}$ being revealed, our algorithm Rand handles
the necessary update in two successive parts:

  * •

first, Rand places $X_{i}$ and $Z_{i}$ next to each other;

  * •

second, Rand places $x_{i}$ and $z_{i}$ next to each other.

We refer to the first part as the _moving_ part of the update, and we refer to
the second part as the _rearranging_ part of the update. Next, we describe how
our algorithm performs those two parts.

Rand performs the moving part exactly like in the clique case above: $X_{i}$
moves with probability $|Z_{i}|/(|X_{i}|+|Z_{i}|)$ and $Z_{i}$ moves with
probability $|X_{i}|/(|X_{i}|+|Z_{i}|)$.

In order to perform the rearranging part of the update, our algorithm has only
two options, one for each of the two orientations of $X_{i}\cup Z_{i}$ in the
permutation. Again, Rand makes its choices by flipping a biased coin weighted
as follows: the probability to make one given choice equals the (normalized)
cost of making the other choice. For a visual description, see Figure 2.

$X_{i}$$Z_{i}$$x_{i}$$z_{i}$$X_{i}$$Z_{i}$$x_{i}$$z_{i}$$X_{i}$$Z_{i}$$z_{i}$$x_{i}$$\begin{subarray}{c}\text{Reverse
}X_{i}\\\ \text{ with probability}\\\
\frac{|X_{i}|\cdot|Z_{i}|+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\end{subarray}$$\begin{subarray}{c}\text{Swap
}X_{i}\text{ with }Z_{i}\text{ and}\\\ \text{reverse }Z_{i}\text{ with
probability}\\\ \frac{\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\end{subarray}$ Figure 2: The two possible actions of
Rand to rearrange the components $X_{i}$ and $Z_{i}$ together for a particular
configuration of the merging components

In the rest of this section, we will prove the following theorem.

######  Theorem 8.

The algorithm Rand is $8\ln n$ competitive for the problem of online MinLA
where the revealed subgraphs $G_{0},\dots G_{k}$ are collections of lines.

###  4.2 Additional Notation for the Proofs

Let $x_{i}$ and $z_{i}$ be the endpoints of the edge that is revealed between
$G_{i}$ and $G_{i+1}$ for all $0\leq i\leq k-1$. Let $\mathcal{C}_{i}$ be the
set of components of $G_{i}$. We call $X_{i},Z_{i}\in\mathcal{C}_{i}$ the
components that contain $x_{i}$ and $z_{i}$ respectively. If
$T,U\in\mathcal{C}_{i}$ are two components, we define:

  * •

$\overrightarrow{T}$ and $\overleftarrow{T}$ are the events that $T$ has one
given orientation or the reversed one (an orientation of a component is the
ordering of its nodes in the permutation). $P[\overrightarrow{T}]$ is the
associated probability that Rand is in a configuration with the orientation
$\overrightarrow{T}$.

  * •

$L_{T,U}$ is the set of all pairs that contain exactly one node from $T$ and
one node from $U$ in any order, i.e., $L_{T,U}=T\times U\cup U\times T$

  * •

$L_{\pi_{i}}$ is the set of all node pairs $(x,y)$ such that $x$ is on the
left of $y$ in $\pi_{i}$.

  * •

$L_{\overrightarrow{T}}$ is the set of all pairs $(t,t^{\prime})$ in $T$ such
that $t$ is on the left of $t^{\prime}$ when $T$ has orientation
$\overrightarrow{T}$.

###  4.3 Upper Bound on the Moving Costs

Calling $M$ the random variable equal to the total moving costs of Rand, the
Theorem 6 of the above clique case can also be applied and it holds that

$\mathbb{E}[M]\leq 4\ln n\cdot|L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}|.$

###  4.4 Upper Bound on the Rearranging Costs

In this subsection, we give an upper bound of the total cost incurred by the
rearranging parts of the updates. We begin our proof by computing the
probability of a component to be one or the other orientation (given in Lemma
10). Right below (Lemma 9) we present an auxiliary result used to derive Lemma
10.

######  Lemma 9.

Consider $N$ real numbers $a_{1},a_{2},\dots,a_{N}$ and $N$ real numbers
$b_{1},b_{2},\dots b_{N}$ each between $0$ and $1$, we call
$\bar{b}_{i}=1-b_{i}$ for all $i\in[N]$. It holds that

$\sum\limits_{t\in\\{0,1\\}^{N}}\left[\sum\limits_{i=1}^{N}t_{i}\cdot
a_{i}\right]\prod\limits_{j=1}^{N}b_{j}^{t_{j}}\cdot\bar{b}_{j}^{\bar{t}_{j}}=\sum\limits_{i=1}^{N}a_{i}\cdot
b_{i}.$

###### Proof.

$\displaystyle\sum\limits_{t\in\\{0,1\\}^{N}}\left[\sum\limits_{i=1}^{N}t_{i}\cdot
a_{i}\right]\prod\limits_{j=1}^{N}b_{j}^{t_{j}}\cdot\bar{b}_{j}^{\bar{t}_{j}}$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\cdot\left[\sum\limits_{t\in\\{0,1\\}^{N}}t_{i}\cdot\prod\limits_{j=1}^{N}b_{j}^{t_{j}}\cdot\bar{b}_{j}^{\bar{t}_{j}}\right]$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\cdot
b_{i}\left[\sum\limits_{\begin{subarray}{c}t\in\\{0,1\\}^{N}\\\
t_{i}=1\end{subarray}}\prod\limits_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}b_{j}^{t_{j}}\cdot\bar{b}_{j}^{\bar{t}_{j}}\right]$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\cdot b_{i}$

The last equality was derived using the total probability formula. ∎

######  Lemma 10.

Let $1\leq i\leq k$. For any $X\in\mathcal{C}_{i}$ containing strictly more
than one node, it holds that

$P[\overrightarrow{X}]=\frac{|L_{\overrightarrow{X}}\cap
L_{\pi_{0}}|}{\left(\begin{subarray}{c}|X|\\\ 2\end{subarray}\right)}.$

###### Proof.

We prove the claim by induction on $i$. The claim clearly holds for $i=1$. Let
$i\in\\{1\dots k\\}$, we assume that the claim holds for $i$ and prove it also
holds for $i+1$. We distinguish between cases depending on the size of the
merging components $X_{i}$ and $Z_{i}$.

  * •

If both $X_{i}$ and $Z_{i}$ have size one, the claim clearly holds.

  * •

If only one of $X_{i}$ or $Z_{i}$ have size one, say $X_{i}$. In the
following, we assume that the orientation $\overrightarrow{X_{i}\cup Z_{i}}$
refers to $X_{i}$ being on the left of $Z_{i}$ and $Z_{i}$ having the
orientation $\overrightarrow{Z_{i}}$.

$\displaystyle P[\overrightarrow{X_{i}\cup Z_{i}}]$
$\displaystyle=P[X_{i}\textrm{---}Z_{i}]\cdot
P[\overrightarrow{Z_{i}}]+\frac{|Z_{i}|}{\left(\begin{subarray}{c}|Z_{i}|+1\\\
2\end{subarray}\right)}\cdot P[X_{i}\textrm{---}Z_{i}]\cdot
P[\overleftarrow{Z_{i}}]+\frac{\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|Z_{i}|+1\\\
2\end{subarray}\right)}\cdot P[\overrightarrow{Z_{i}}]\cdot
P[Z_{i}\textrm{---}X_{i}]$
$\displaystyle=\frac{|Z_{i}|}{\left(\begin{subarray}{c}|Z_{i}|+1\\\
2\end{subarray}\right)}\cdot
P[X_{i}\textrm{---}Z_{i}]+\frac{\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|Z_{i}|+1\\\
2\end{subarray}\right)}\cdot P[\overrightarrow{Z_{i}}]$
$\displaystyle=\frac{|X_{i}\times Z_{i}\cap
L_{\pi_{0}}|+|L_{\overrightarrow{Z_{i}}}\cap
L_{\pi_{0}}|}{\left(\begin{subarray}{c}|Z_{i}|+1\\\ 2\end{subarray}\right)}$
$\displaystyle=\frac{|L_{\overrightarrow{X_{i}\cup Z_{i}}}\cap
L_{\pi_{0}}|}{\left(\begin{subarray}{c}|Z_{i}|+1\\\ 2\end{subarray}\right)}$

which proves the claim. We used the induction hypothesis and Lemma 3 in the
above calculations.

  * •

Assume now that neither $X_{i}$ nor $Z_{i}$ have size one. To prove the
results, we use Lemma 9 with the following values: $N=3$, index $a_{1}$ refers
to the cost to reverse $X_{i}$, $a_{2}$ is the cost to swap $X_{i}$ and
$Z_{i}$, $a_{3}$ is the cost to reverse $Z_{i}$,
$b_{1}=P[\overleftarrow{X_{i}}]$, $b_{2}=P[Z_{i}\textrm{---}X_{i}]$,
$b_{3}=P[\overleftarrow{Z_{i}}]$. With those parameters (and with the $a_{j}$s
divided by $\left(\begin{subarray}{c}|X_{i}+Z_{i}|\\\
2\end{subarray}\right)$), the left term of Lemma 9 equals
$P[\overrightarrow{X_{i}\cup Z_{i}}]$, where $\overrightarrow{X_{i}\cup
Z_{i}}$ stands for the orientation where $\overrightarrow{X_{i}}$,
$X_{i}\textrm{---}Z_{i}$ and $\overrightarrow{Z_{i}}$. Using Lemma 9, it
therefore holds:

$P[\overrightarrow{X_{i}\cup
Z_{i}}]=\frac{1}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\cdot\left(\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)\cdot P[\overrightarrow{X_{i}}]+|X_{i}||Z_{i}|\cdot
P[X_{i}\textrm{---}Z_{i}]+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)\cdot P[\overrightarrow{Z_{i}}]\right).$

Using the induction hypothesis and Lemma 3, we obtain

$\displaystyle P[\overrightarrow{X_{i}\cup Z_{i}}]$
$\displaystyle=\frac{1}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\cdot\left(|L_{\overrightarrow{X_{i}}}\cap
L_{\pi_{0}}|+|X_{i}\times Z_{i}\cap
L_{\pi_{0}}|+|L_{\overrightarrow{Z_{i}}}\cap L_{\pi_{0}}|\right)$
$\displaystyle=\frac{|L_{\overrightarrow{X_{i}\cup Z_{i}}}\cap
L_{\pi_{0}}|}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)},$

which ends this case.

We investigated all possible three cases hence the claim also holds after
$G_{i+1}$ was revealed. By induction, the claim holds for any $i+1$. ∎

Next, we state an auxiliary lemma that is later used to prove Lemma 12.

######  Lemma 11.

Let be $N$ real numbers $a_{1},a_{2},\dots a_{N}$. Let be $N$ real numbers
$b_{1},b_{2},\dots b_{N}$ each between $0$ and $1$, we call
$\bar{b}_{i}=1-b_{i}$ for all $i\in\\{1\dots N\\}$. It holds that

$\displaystyle\sum\limits_{t\in\\{0,1\\}^{N}}$
$\displaystyle\left[\sum\limits_{i=1}^{N}\bar{t}_{i}\cdot
a_{i}\right]\cdot\left[\sum\limits_{i=1}^{N}t_{i}\cdot
a_{i}\right]\prod\limits_{k=1}^{N}b_{k}^{t_{k}}\cdot\bar{b}_{k}^{\bar{t}_{k}}\leq\sum\limits_{i=1}^{N}b_{i}a_{i}\left(A-a_{i}\right),$

where $A=\sum_{i=1}^{N}a_{i}$.

###### Proof.

$\displaystyle\sum\limits_{t\in\\{0,1\\}^{N}}\left[\sum\limits_{i=1}^{N}t_{i}\cdot
a_{i}\right]\cdot\left[\sum\limits_{j=1}^{N}\bar{t}_{j}\cdot
a_{j}\right]\prod\limits_{k=1}^{N}b_{k}^{t_{k}}\cdot\bar{b}_{k}^{\bar{t}_{k}}$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\sum\limits_{\begin{subarray}{c}t\in\\{0,1\\}^{N}\\\
t_{i}=1\end{subarray}}\left[\sum\limits_{j=1}^{N}\bar{t}_{j}\cdot
a_{j}\right]\prod\limits_{k=1}^{N}b_{k}^{t_{k}}\cdot\bar{b}_{k}^{\bar{t}_{k}}$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\cdot
b_{i}\sum\limits_{\begin{subarray}{c}t\in\\{0,1\\}^{N}\\\
t_{i}=1\end{subarray}}\left[\sum\limits_{j=1}^{N}\bar{t}_{j}\cdot
a_{j}\right]\prod\limits_{\begin{subarray}{c}k=1\\\ k\neq
i\end{subarray}}^{N}b_{k}^{t_{k}}\cdot\bar{b}_{k}^{\bar{t}_{k}}$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\cdot
b_{i}\sum\limits_{\begin{subarray}{c}t\in\\{0,1\\}^{N}\\\
t_{i}=1\end{subarray}}\left(\left[\sum\limits_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}\bar{t}_{j}\cdot
a_{j}\right]\prod\limits_{\begin{subarray}{c}k=1\\\ k\neq
i\end{subarray}}^{N}b_{k}^{t_{k}}\cdot\bar{b}_{k}^{\bar{t}_{k}}\right)$
$\displaystyle=\sum\limits_{i=1}^{N}a_{i}\cdot
b_{i}\left[\sum\limits_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{N}a_{j}\cdot b_{j}\right]$
$\displaystyle\leq\sum\limits_{i=1}^{N}a_{i}\cdot b_{i}\left(A-a_{i}\right).$

We used Lemma 9 from line 4 to line 5, and used that $b_{i}\leq 1$ for the
last inequality. ∎

######  Lemma 12.

Let $i\in\\{0\dots k-1\\}$. Let $R_{X_{i},Z_{i}}$ be the cost of the
rearranging part of the update that follows the reveal of $G_{i+1}$. The
following holds:

$\displaystyle\frac{1}{2}\mathbb{E}\left[R_{X_{i},Z_{i}}\right]$
$\displaystyle\leq|(L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{X_{i},X_{i}}|\cdot\frac{|X_{i}||Z_{i}|+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}+|(L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{X_{i},Z_{i}}|\cdot\frac{\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}$ $\displaystyle\quad\quad+|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{Z_{i},Z_{i}}|\cdot\frac{|X_{i}||Z_{i}|+\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}.$

###### Proof.

In its final permutation $\pi_{k}^{\textsc{Opt}}$, the optimal offline
algorithm Opt must have chosen one configuration for each component. In
particular, Opt chose one configuration for the orientation of $X_{i}$, one
for the relative position of $X_{i}$ and $Z_{i}$, and one for the orientation
of $Z_{i}$. Without loss of generality, we assume that Opt configured $X_{i}$
and $Z_{i}$ as follows: $\overleftarrow{X_{i}}$, $Z_{i}\textrm{---}X_{i}$ and
$\overleftarrow{Z_{i}}$. In that case, we use Lemma 11 with the following
values: $N=3$, $a_{1}=\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)$, $a_{2}=|X_{i}|\cdot|Z_{i}|$,
$a_{3}=\left(\begin{subarray}{c}|Z_{i}|\\\ 2\end{subarray}\right)$,
$b_{1}=P[\overrightarrow{X_{i}}]$ $b_{2}=P[X_{i}\textrm{---}Z_{i}]$ and
$b_{3}=P[\overrightarrow{Z_{i}}]$. The obtained expression corresponds to the
expected value of $R_{X_{i},Z_{i}}$ if we divide it by
$\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\ 2\end{subarray}\right)/2$. We use
the inequality of Lemma 11 and then Lemma 10 to replace the probabilities by
their expressions. Finally, we perform the same reasoning as in Lemma 4 to
link our upper bound with the final permutation of Opt and obtain the claim. ∎

Next, we state an auxiliary lemma that is useful in the proof the next
theorem.

######  Lemma 13.

Let $s_{1},s_{2},\dots s_{N}$ be a series of strictly positive natural
numbers, let $S=\sum_{i=1}^{N}s_{i}$ be their sum. It holds:

$\displaystyle\sum_{i=1}^{N}\frac{s_{i}^{2}}{\left(\begin{subarray}{c}\sum_{j=1}^{i}s_{j}\\\
2\end{subarray}\right)}\leq 2H_{S}$ and
$\displaystyle\sum_{i=2}^{N}\frac{s_{i-1}\cdot
s_{i}}{\left(\begin{subarray}{c}\sum_{j=2}^{i}s_{j}\\\
2\end{subarray}\right)}\leq 2H_{S}.$

where $H_{S}=1+\frac{1}{2}+\dots\frac{1}{S}$ is the harmonic sum until the
$S$-the term.

###### Proof.

Proving the first inequality is direct since all the terms of its left member
are smaller than those of lemma 5. We now prove the second inequality.

$\displaystyle\sum_{i=2}^{N}\frac{s_{i-1}\cdot
s_{i}}{\left(\begin{subarray}{c}\sum_{j=2}^{i}s_{j}\\\
2\end{subarray}\right)}$ $\displaystyle\leq
2\sum_{i=2}^{N}\frac{s_{i-1}}{\sum_{j=2}^{i-1}s_{j}}\cdot\frac{s_{i}}{\sum_{j=2}^{i}s_{j}}$
$\displaystyle\leq
2\sqrt{\sum_{i=2}^{N}\left(\frac{s_{i-1}}{\sum_{j=2}^{i-1}s_{j}}\right)^{2}}\cdot\sqrt{\sum_{i=2}^{N}\left(\frac{s_{i}}{\sum_{j=2}^{i}s_{j}}\right)^{2}}$
$\displaystyle\leq 2H_{S}$

We used the Cauchy-Schwarz inequality in the second line. ∎

######  Theorem 14.

Calling $M$ and $R$ respectively the moving and rearranging costs of Rand, it
holds that

$\displaystyle\mathbb{E}[M+R]\leq 8H_{n}\cdot|L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}|$

where $H_{n}$ is the harmonic sum.

###### Proof.

We first derive an upper bound of the expected value of $R$.

$\displaystyle\frac{1}{2}\mathbb{E}[R]$
$\displaystyle=\sum\limits_{i=0}^{k-1}\frac{1}{2}\mathbb{E}[R_{X_{i},Z_{i}}]$
$\displaystyle\leq\sum\limits_{i=0}^{k-1}|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{X_{i},X_{i}}|\cdot\frac{|X_{i}||Z_{i}|+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}+|(L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{X_{i},Z_{i}}|\cdot\frac{\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}$
$\displaystyle\quad\quad\quad\quad+|(L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}})\cap
L_{Z_{i},Z_{i}}|\cdot\frac{|X_{i}||Z_{i}|+\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}$ $\displaystyle=\sum\limits_{p\in L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}}\sum\limits_{i=0}^{k-1}\frac{|X_{i}||Z_{i}|+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\cdot\mathbbm{1}(p\in
L_{X_{i},X_{i}})+\frac{\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)+\left(\begin{subarray}{c}|Z_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\cdot\mathbbm{1}(p\in L_{X_{i},Z_{i}})$
$\displaystyle\quad\quad\quad\quad+\frac{|X_{i}||Z_{i}|+\left(\begin{subarray}{c}|X_{i}|\\\
2\end{subarray}\right)}{\left(\begin{subarray}{c}|X_{i}|+|Z_{i}|\\\
2\end{subarray}\right)}\cdot\mathbbm{1}(p\in L_{Z_{i},Z_{i}})$ (2)

Combining the upper bound (2) above with the upper bound (1) in the proof of
Theorem 6, we now have upper bounds for the expected costs of both moving and
rearranging parts of the updates, and hence for the total expected cost of
Rand.

Let $p\in L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}}$ and let $y\in p$.
In the upper bounds (1) and (2), we sum and upper-bound all the positive
coefficients associated with node $y$ and pair $p$. In case the nodes of $p$
never belong to the same component then the upper bound of Theorem 6 then the
upper bound (1) will be sufficient for that pair. We now assume that the nodes
of $p$ eventually belong to the same component, let $i_{p}$ be the request
index when this happens.

Using the upper bound (1) and the same reasoning as in Theorem 6, we find that
the sum of the positive coefficients associated to $y$ and $p$ is no greater
than $4H_{i_{p}}$ from revealed subgraphs $G_{1}$ to $G_{i_{p}}$. We now
upper-bound the cost associated to $y$ and $p$ after $i_{p}$ using (2). Let
$Y_{i_{p}}\dots Y_{N}$ be the components that successively merge with $y$’s
component after $i_{p}$: $Y_{i_{p}}$ is the component that contains the other
node in $p$. We can associate the rearranging cost paid during the $i_{p}$’s
update with the coefficient $\Big{(}\left(\begin{subarray}{c}|Y_{i_{p}}|\\\
2\end{subarray}\right)+\left(\begin{subarray}{c}|Y_{i_{p}-1}|\\\
2\end{subarray}\right)\Big{)}/\left(\begin{subarray}{c}|Y_{i_{p}}|+|Y_{i_{p}-1}|\\\
2\end{subarray}\right)$ in the sum. All the rearranging costs paid after the
$i_{p}$’s update are associated with the coefficients
$\Big{(}|Y_{i+1}|\cdot|Y_{i}|+\left(\begin{subarray}{c}|Y_{i+1}|\\\
2\end{subarray}\right)\Big{)}/\left(\begin{subarray}{c}|Y_{i+1}|+|Y_{i|}|\\\
2\end{subarray}\right)$. Hence, by applying Lemma 13 for those coefficients,
we obtain that the expected cost incurred between request indices $i_{p}$ and
$k$ is no greater than $4(H_{k}-H_{i_{p}})$ for $y$ in the pair $p$. Applying
this reasoning for the two nodes in each pair $p\in L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}$, we finally have that

$\mathbb{E}[M+R]\leq\sum\limits_{p\in L_{\pi_{0}}\setminus
L_{\pi_{k}^{\textsc{Opt}}}}4H_{i_{p}}+8(H_{k}-H_{i_{p}})\leq
8H_{n}\cdot|L_{\pi_{0}}\setminus L_{\pi_{k}^{\textsc{Opt}}}|,$

which ends the proof. ∎

Finally, using the above Theorem 14 with the Observation 7 directly proves
Theorem 8.

##  5 Lower Bounds

In this section, we show tightness of our analysis. First, we show a lower
bound for any randomized online algorithm, concluding that our randomized
algorithm is asymptotically optimal among all online randomized algorithms.
Second, we show a weaker lower bound for the competitiveness of the
deterministic algorithms belonging to the family of algorithms considered in
Section 2, concluding that our analysis of this family is tight; however the
question whether this family is optimally competitive remains open.

###  5.1 A Lower Bound of $\Omega(\log n)$ for any Randomized Algorithm

The lower bound is an adaptation of the lower bound given by Olver et al. for
the _itinerant list update problem_ [25]. This theorem gives an asymptotically
tight lower bound to complement Theorems 2 and 8.

######  Theorem 15.

If a randomized online algorithm for the online minimum linear arrangement is
$c$-competitive, then $c\geq\frac{1}{16}\cdot\log n$.

###### Proof.

We apply Yao’s principle to derive the lower bound. We construct a
distribution of request sequences in the following way. Let $n$ be a power of
$2$ so that $n=2^{q}$, and $q=\log n$. First, we choose a random permutation
$P$ of the $n$ nodes. Then, we construct a balanced binary tree whose leaves
are the permutation $P$ and the internal nodes are added to form the tree.
Then, we request pairs of nodes as follows. We traverse the tree level by
level bottom-up starting from the penultimate level. For each internal node
$z$ of the current level of binary tree, we issue a request between the two
leaves, $u$ and $v$, chosen by following a line in the tree from the internal
node until we encounter a leaf. Concretely, to obtain the leaf $u$, we first
descend from $z$ towards its left child once, and then we continue to descend
to the right child until a leaf is reached. To obtain the leaf $v$, we first
descend from $z$ to its right child once, and then we continue to descend to
the left child until a leaf is reached.

Any optimal offline algorithm pays at most $n^{2}$ for the constructed
sequence of requests. Consider an offline algorithm Off that orders the leaves
according to $P$ at the beginning and then does not move. Off produces a
feasible solution since all requests are between neighbors in $P$. Any optimal
offline algorithm pays no more than Off.

Fix any deterministic online algorithm Alg. We show that Alg pays at least
$\Omega(n^{2}\cdot\log n)$ to serve the requests. To this end, we will show
that on the request issued at each level of the binary tree, Alg pays at least
$\frac{1}{8}n^{2}$. Before the requests of the level $i$ arrives, Alg has
$2^{i}$ components, each of size $2^{q-i}$. We claim that the expected cost of
Alg on the $j$-th request is $(2^{i-1}+j)\cdot 2^{2(q-i)}$. First, assume that
Alg moves components only after their nodes are requested. At the $j$-th
request, we have exactly $2^{i}-2j$ components not requested in this round. As
requests are issued accordingly to a random permutation, for the $j$-th
request the number of components not yet requested at this level between the
requested nodes is at least $(2^{i}-2j)/2$. The requested components must be
collocated, hence for each of such components in between, swapping its
position with the requested component costs $(2^{q-i})^{2}$. In total, the
cost for the $j$-th request is at least

$\sum_{j=1}^{2^{i-1}}(2^{i-1}-j)\cdot(2^{q-i})^{2}=2^{2q-3}=\frac{1}{8}n^{2}.$

Second, if Alg moves some components before they are requested, each such swap
could reduce the migration cost for the requests at the current level by at
most $2$, hence the cost of Alg for the requests at the current level is at
least $\frac{1}{16}n^{2}$.

Summing over the $q=\log n$ levels results in the total cost at least
$\frac{1}{16}n^{2}\cdot\log n$, whereas any optimal offline algorithm pays at
most $n^{2}$, which concludes the proof. ∎

###  5.2 A Lower Bound of $\Omega(n)$ for a Family of Deterministic Algorithms

Now, we give a lower bound of $\Omega(n)$ for competitiveness of the family of
algorithms introduced in Section 2. Combined with Theorem 1, it implies that
our analysis of these algorithms is tight. However, the question whether the
competitiveness of _any_ deterministic online algorithm is linear remains
unresolved.

######  Theorem 16.

Any deterministic online algorithm that always moves to any feasible
permutation with the lowest distance to $\pi_{0}$ is no better than
$\Omega(n)$-competitive.

###### Proof.

Fix any deterministic algorithm Alg that always moves to any feasible
permutation with the lowest distance to $\pi_{0}$. Consider any line topology
with an odd number of nodes, and let $x$ be a node in the middle of the line.

We construct the sequence of requests as follows. Let $y_{1}$ and $y_{2}$ be
the nodes directly on the left and right of $x$. First, we request $y_{1}$ and
$y_{2}$, and refer to $Y_{2}$ as the component containing $y_{1}$ and $y_{2}$.
To serve this request, Alg must place $Y_{2}$ either on the left or on the
right of $x$. Let $y_{3}$ be the neighbor of $x$ such that $x$ is between
$y_{3}$ and $Y_{2}$ — this node exists since putting $x$ at one end is not a
closest permutation to $\pi_{0}$. Then, we request $y_{3}$ and a node from
$Y_{2}$. We end up with component $Y_{3}=\\{y_{1},y_{2},y_{3}\\}$. We continue
to issue requests growing the component $Y_{i}$ by issuing a request to the
neighbor of $x$ that neighbors $x$ but is not contained in the component
$Y_{i}$. We continue this process until we have one component of size $n-1$
and $x$ alone.

The cost of an optimal offline solution is at most $n$, since the nodes in
$Y_{n-1}$ have the same internal order as in $\pi_{0}$, so an offline
algorithm can serve all the requests by moving $x$ to either the leftmost or
the rightmost position on the line and then no further node movements are
necessary.

We claim that Alg pays $\Omega(n^{2})$ for this sequence of requests. Since
Alg moves to a permutation closest to $\pi_{0}$, $x$ alternates between the
left and the right side of the growing component $Y_{i}$. Below we prove that
this behavior must occur. Let $L$ be the set of nodes that were on the left
side of $x$ in the initial configuration, $R$ for the nodes on the right. Let
$Y_{i}$ be the growing component after $i$ requests. We first show that: In
$Y_{i}$, there are strictly more nodes from $L$ than $R$, and hence $x$ is on
the right of $Y_{i}$ Likewise, In $Y_{i}$, there are strictly more nodes from
$R$ than $L$, and hence $x$ is on the left of $Y_{i}$. This is true since Alg
moves to a permutation with the smallest distance to $\pi_{0}$. Hence, any
node from $L$ will stay on the left of $x$ as long as it is not requested, and
the equivalent statement holds for $R$. Since the ordering within $Y_{i}$ is
forced, the only ordering that ALG could change is the order between $x$ and
$S_{i}$, hence the result. Now, notice that: If $x$ is on the left of $Y_{i}$
then the next request will add a node from $L$ into $Y_{i+1}$ If $x$ is on the
right of $Y_{i}$ then the next request will add a node from $R$ into
$Y_{i+1}$. The nodes in $Y_{i+1}$ belong to either $L$ or $R$, and at all
times we either have a majority of nodes from $L$ or from $R$. The majority of
nodes within $Y$ will change every second request. Each time the majority
changes, $x$ and $Y$ change their relative positions, which incurs a final
cost of $\Omega(n^{2})$ for Alg.

The cost of the optimal solution is at most $O(n)$, and the cost of Alg is
$\Omega(n^{2})$, hence the competitive ratio of Alg is $\Omega(n)$. ∎

As a result of the theorems in this section, the analysis of our deterministic
and the randomized algorithms is tight. Furthermore, our randomized algorithm
attains asymptotically optimal competitive ratio among all randomized online
algorithms.

##  6 Conclusions

This paper considered a fundamental online variant of the minimum linear
arrangement problem. The problem is motivated by the goal of understanding how
to efficiently adjust virtual network embeddings. Our main contribution is a
tight randomized online algorithms for this problem in a restricted case where
the to-be-embedded graph is either a collection of lines or a collection of
cliques. An interesting open research question is whether online algorithms
can attain the logarithmic competitive ratio also for general graphs.

## References

  * [1] N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor.  The online set cover problem.  SIAM J. Comput., 39(2):361–370, 2009.
  * [2] C. Ambühl, M. Mastrolilli, and O. Svensson.  Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut.  SIAM Journal on Computing, 40(2):567–596, 2011.
  * [3] C. Avin, M. Bienkowski, A. Loukas, M. Pacut, and S. Schmid.  Dynamic balanced graph partitioning.  SIAM J. Discret. Math., 34(3):1791–1812, 2020.
  * [4] C. Avin, I. van Duijn, M. Pacut, and S. Schmid.  Self-adjusting grid networks.  Information and Computation, 292, 2023.
  * [5] J. Balogh, J. Békési, G. Dósa, L. Epstein, and A. Levin.  A new and improved algorithm for online bin packing.  In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 5:1–5:14, 2018.
  * [6] J. Bhasker and S. Sahni.  Optimal linear arrangement of circuit components.  Journal of VLSI and computer systems, 2, 03 2002.
  * [7] M. Bienkowski, M. Böhm, M. Koutecký, T. Rothvoß, J. Sgall, and P. Veselý.  Improved analysis of online balanced clustering.  Approximation and Online Algorithms - International Workshop (WAOA), 2021.
  * [8] M. Bienkowski and G. Even.  An improved approximation algorithm for dynamic minimum linear arrangement.  In 41st International Symposium on Theoretical Aspects of Computer Science, (STACS), volume 289 of LIPIcs, pages 15:1–15:19, 2024\.
  * [9] A. Borodin and R. El-Yaniv.  Online Computation and Competitive Analysis.  1998\.
  * [10] N. Buchbinder and J. Naor.  The design of competitive online algorithms via a primal-dual approach.  Found. Trends Theor. Comput. Sci., 3(2-3):93–263, 2009.
  * [11] M. Chowdhury, M. R. Rahman, and R. Boutaba.  Vineyard: Virtual network embedding algorithms with coordinated node and link mapping.  IEEE/ACM Trans. Netw., 20(1):206–219, 2012.
  * [12] J. Díaz, J. Petit, and M. Serna.  A survey of graph layout problems.  ACM Comput. Surv., 34(3):313–356, 2002.
  * [13] M. Eikel, C. Scheideler, and A. Setzer.  Minimum linear arrangement of series-parallel graphs.  In Approximation and Online Algorithms - 12th International Workshop (WAOA), volume 8952 of Lecture Notes in Computer Science, pages 168–180. Springer, 2014.
  * [14] L. Epstein and M. Levy.  Online interval coloring and variants.  In Automata, Languages and Programming, pages 602–613, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [15] S. Even.  Np-completeness of several arrangement problems.  Technical Report; Department of computer Science, 43, 1975.
  * [16] A. Fischer, J. F. Botero, M. T. Beck, H. de Meer, and X. Hesselbach.  Virtual network embedding: A survey.  IEEE Commun. Surv. Tutorials, 15(4):1888–1906, 2013.
  * [17] B. Gamlath, M. Kapralov, A. Maggiori, O. Svensson, and D. Wajc.  Online matching with general arrivals.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019.
  * [18] M. M. Halldórsson, K. Iwama, S. Miyazaki, and S. Taketomi.  Online independent sets.  Theoretical Computer Science, 289(2):953–962, 2002.  Computing and Combinatorics.
  * [19] L. H. Harper.  Optimal assignments of numbers to vertices.  Journal of The Society for Industrial and Applied Mathematics, 12:131–135, 1964.
  * [20] M. Henzinger, S. Neumann, H. Räcke, and S. Schmid.  Tight bounds for online graph partitioning.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021.
  * [21] M. Henzinger, S. Neumann, and S. Schmid.  Efficient distributed workload (re-)embedding.  In 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems. ACM, 2019.
  * [22] A. Mehta.  Online matching and ad allocation.  Foundations and Trends in Theoretical Computer Science (FOCS), 8(4):265–368, 2013.
  * [23] M. Miller, R. S. Rajan, N. Parthiban, and I. Rajasingh.  Minimum Linear Arrangement of Incomplete Hypercubes.  The Computer Journal, 58(2):331–337, 2013.
  * [24] J. C. Mogul and L. Popa.  What we talk about when we talk about cloud network performance.  ACM SIGCOMM Computer Communication Review, 42(5):44–48, 2012.
  * [25] N. Olver, K. Pruhs, K. Schewior, R. Sitters, and L. Stougie.  The itinerant list update problem.  In Approximation and Online Algorithms, 2018.
  * [26] M. Pacut, M. Parham, and S. Schmid.  Optimal online balanced graph partitioning.  In 40th IEEE Conference on Computer Communications, INFOCOM 2021, Vancouver, BC, Canada, May 10-13, 2021, pages 1–9, 2020.
  * [27] J. Petit.  Experiments on the minimum linear arrangement problem.  ACM J. Exp. Algorithmics, 8, 2004.
  * [28] S. J. Phillips and J. R. Westbrook.  Online load balancing and network flow.  In ACM Symposium on Theory of Computing (STOC), pages 402–411, 1993.
  * [29] S. Rao and A. W. Richa.  New approximation techniques for some linear ordering problems.  SIAM J. Comput., 34(2):388–404, 2004.
  * [30] M. Rost and S. Schmid.  Charting the complexity landscape of virtual network embeddings.  In IFIP Networking Conference, pages 55–63, 2018.
  * [31] M. Rost and S. Schmid.  Virtual network embedding approximations: Leveraging randomized rounding.  IEEE/ACM Trans. Netw., 27(5):2071–2084, 2019.
  * [32] A. Roy, H. Zeng, J. Bagga, G. Porter, and A. C. Snoeren.  Inside the social network’s (datacenter) network.  In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, pages 123–137, 2015.
  * [33] S. S. Seiden.  On the online bin packing problem.  J. ACM, 49(5):640–671, 2002.
  * [34] Y. Shiloach.  A minimum linear arrangement algorithm for undirected trees.  SIAM Journal on Computing, 8(1):15–32, 1979.
  * [35] S. Vishwanathan.  Randomized online graph coloring.  Journal of Algorithms, 13(4):657–669, 1992.