An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement

elements subject to a sequence of edge requests. The input consists of a sequence
of $m$ edges (i.e., unordered pairs of elements). The output is a sequence of
permutations (i.e., bijective mapping of the elements to $n$ equidistant
points). In step $t$, the order of the elements is changed to the $t$-th
permutation, and then the $t$-th request is served. The cost of the output
consists of two parts per step: request cost and rearrangement cost. The former
is the current distance between the endpoints of the request, while the
latter is proportional to the number of adjacent element swaps
required to move from one permutation to the consecutive permutation.
The goal is to find a minimum cost solution.

We present a deterministic $O(\log n \log\log n)$-approximation algorithm for
this problem, improving over a randomized $O(\log^2 n)$-approximation by [Olver
et al., 2018]. Our algorithm is based on solving spreading-metric
LP relaxation on a time-expanded graph, applying a tree decomposition on the
basis of the LP solution, and finally converting the tree decomposition to a
sequence of permutations. The techniques we employ are general and have the
potential to be useful for other dynamic graph optimization problems.

Joint work with Marcin Bienkowski.