Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the plane

Abstract

Given a set $P$ of $n$ points with their pairwise distances, the traveling salesman problem (TSP) asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the $l_1$ distance. In this paper, a fixed-parameter algorithm for the Rectilinear TSP is presented and relies on techniques for solving TSP on bounded-treewidth graphs. It proves that the problem can be solved in $O\left(nh{7}^h\right)$ where $h\le n$ denotes the number of horizontal lines containing the points of $P$. The same technique can be directly applied to the problem of finding a shortest rectilinear Steiner tree that interconnects the points of $P$ providing a $O\left(nh{5}^h\right)$ time complexity. Both bounds improve over the best time bounds known for these problems.

24 pages, 13 figures, 6 tables

References in corpus (1)

• Optimally solving the joint order batching and picker routing problem

Cited by in corpus (3)

• Solving Optimization Problems through Fully Convolutional Networks: an Application to the Travelling Salesman Problem
• A note on the complexity of the picker routing problem in multi-block warehouses and related problems
• Exact algorithms for the order picking problem