Name
Abstract | ||
|---|---|---|
Given a graph $G=(V,E)$ with $V={1,ldots,n}$, we place on every vertex a token $T_1,ldots,T_n$. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token $T_i$ is on vertex $i$. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out $2^{o(n)}$ algorithm under ETH. This is matched with a simple $2^{O(nlog n)}$ algorithm based on dynamic programming. We give a general $4$-approximation algorithm and show APX-hardness. Thus, there is a small constant $deltau003e1$ such that every polynomial time approximation algorithm has approximation factor at least $delta$. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Computational Complexity | Discrete mathematics,Binary logarithm,Swap (computer programming),Dynamic programming,Approximation algorithm,Combinatorics,Vertex (geometry),Upper and lower bounds,Security token,Mathematics,Goto |
DocType | Volume | Citations |
Journal | abs/1602.05150 | 0 |
PageRank | References | Authors |
0.34 | 6 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tillmann Miltzow | 1 | 37 | 16.31 |
| Lothar Narrins | 2 | 0 | 0.34 |
| Yoshio Okamoto | 3 | 170 | 28.50 |
| Günter Rote | 4 | 1181 | 129.29 |
| Antonis Thomas | 5 | 1 | 0.69 |
| Takeaki Uno | 6 | 1319 | 107.99 |