Yike Chen: An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies

Speaker:

Yike Chen (University of Electronic Science and Technology of China)

Time:

16:20-17:20 (Time in Beijing)
November 15, 2024 (Friday)

Venue:

518, Research Building 4

Abstract:

The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem where a crane must traverse a graph with designated pairs of pickup and delivery points, moving objects from each pickup location to its corresponding delivery point. The objective is to minimize the total travel distance. SCP is known to be NP-hard, even on trees. Polynomial-time results are limited to graphs topologically equivalent to a path or cycle. In this work, we propose an algorithm that is optimal for each fixed topology, with near-linear runtime. This is made possible by showing that SCP is fixed-parameter tractable (FPT) when parameterized by cycle rank and the number of branch vertices.