Homepage
Andreas Westerlund
Tree-relaxations of relatives to the Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is one of the most well-known and studied combinatorial optimization problems. It is NP-hard, and exact solution approaches therefore have exponential worst-case time complexity (unless P = NP). When attempting to solve this problem, by for example branch-and-bound, it is of great importance to be able to compute lower bounds to the optimal tour length by solving relaxed (less constrained) problems.
In the famous paper by Held and Karp (1970), the concept of a 1-tree relaxation was introduced and used as subproblem in a successful branch-and-bound algorithm.
We consider problems related to TSP, such as the Prize Collecting Traveling Salesman Problem (PCTSP) and the Vehicle Routing Problem (VRP), and study relatives to the Held and Karp 1-tree relaxation, with the purpose of computing lower bounds to PCTSP and VRP. We study in particular two relatives, and establish properties of their solutions and give polynomial time algorithms.
References:
Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Operations Research 18, 1138-1162, 1970.
Göthe-Lundgren, M., Larsson, T., and Westerlund, A.: A note on relatives
to the Held and Karp 1-tree problem. Submitted to Operations Research Letters
Sidansvarig: karin.johansson@liu.se
Senast uppdaterad: 2019-12-03