An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908544033357824 |
|---|---|
| author | Chen, Yike Shi, Ke Xu, Chao |
| author_facet | Chen, Yike Shi, Ke Xu, Chao |
| contents | The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on trees. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle.
We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06764 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies Chen, Yike Shi, Ke Xu, Chao Data Structures and Algorithms Optimization and Control The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on trees. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices. |
| title | An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2410.06764 |