Learning Minimum Linear Arrangement of Cliques and Lines
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910459103281152 |
|---|---|
| author | Dallot, Julien Pacut, Maciej Bienkowski, Marcin Melnyk, Darya Schmid, Stefan |
| author_facet | Dallot, Julien Pacut, Maciej Bienkowski, Marcin Melnyk, Darya Schmid, Stefan |
| contents | 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 $Ω(\ln n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15963 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning Minimum Linear Arrangement of Cliques and Lines Dallot, Julien Pacut, Maciej Bienkowski, Marcin Melnyk, Darya Schmid, Stefan Data Structures and Algorithms 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 $Ω(\ln n)$. |
| title | Learning Minimum Linear Arrangement of Cliques and Lines |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.15963 |