25. A solvable case of the Path-TSP on Van der Veen distance matrices
Invited abstract in session TE-1: Travelling salesperson, stream Travelling salesperson.
Thursday, 16:30 - 18:00Room: L226
Authors (first author is the speaker)
| 1. | Eranda Cela
|
| Department of Discrete Mathematics, TU Graz | |
| 2. | Vladimir Deineko
|
| Warwick Business School | |
| 3. | Gerhard Woeginger
|
| RWTH Aachen |
Abstract
In the Path-TSP, the travelling salesman is looking for the shortest (s, t)-TSP-path, i.e. a path which starts at a given city s and ends at another given city t, after visiting every city exactly once.
In this work we present a polynomially solvable case of the Path-TSP, where the distance matrix of the cities is a Van der Veen matrix (as defined in [1],[2] below).
We investigate the combinatorial structure of the optimal solutions and observe first that it can be characterized by means of certain forbidden patterns. This allows us to restrict the search for optimal solutions on the particular set P of (s,t)-TSP-paths which do not contain the forbidden patterns. While the cardinality of P is exponential in the number n of cities, each path in P can be obtained by patching together simply structured paths of four types, each of them being well amenable to dynamic programming. These specific dynamic programming procedures can be combined to efficiently optimize over P. To this end we distinguish three particular cases: (i) (s,t)=(1,n), (ii) s=1 and t is arbitrary and (iii) s and t are both arbitrary. In Case (i) we show that the Path-TSP can be equivalently transformed to a directed shortest path problem on an auxiliary graph with $O(n)$ vertices. The analysis of the two further case is incremental and builds upon optimal solutions of suitably chosen smaller instances of Case (i) by exploiting the fact that submatrices of a Van der Veen matrix are again Van der Veen matrices.
A straightforward analysis of the constructive steps leads to a
dynamic programming algorithm with cubic time complexity for the general case. It takes a clever implementation and a careful analysis to obtain a quadratic algorithm. Thus a Van der Veen instance of the Path-TSP with $n$ cities can be solved in quadratic time. Obviously this result is best possible (as compared to the size of the input).
References:
[1] V.G. Deineko, B. Klinz, A. Tiskin, and G.J. Woeginger (2014),
Four-point conditions for the TSP: the complete classification.
Discrete Optimization 14, 147-159.
[2] J.A.A. Van der Veen (1994),
A new class of pyramidally solvable symmetric traveling salesman problems.
SIAM J. Discr. Math. 7, 585-592.
Keywords
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers