26 listopada 2024 11:15
[Seminarium ZOK] Marcin Bieńkowski: An Improved Approximation Algorithm for Dynamic Minimum Linear Arrangement
Abstract: The dynamic offline linear arrangement problem deals with
reordering n 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. Our algorithm is based on first 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 Guy Even.