A priori TSP in the scenario model
Martijn van Ee (Vrije Universiteit Amsterdam)
Leo Van van Iersel (TU Delft - Discrete Mathematics and Optimization)
Teun Janssen (TU Delft - Discrete Mathematics and Optimization)
René Sitters (Vrije Universiteit Amsterdam, Centrum Wiskunde & Informatica (CWI))
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
In this paper, we consider the a priori traveling salesman problem in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour. We show that this problem is already NP-hard and APX-hard when all scenarios have size four. On the positive side, we show that there exists a constant-factor approximation algorithm in three restricted cases: if the number of scenarios is fixed, if the number of missing vertices per scenario is bounded by a constant, and if the scenarios are nested. Finally, we discuss an elegant relation with an a priori minimum spanning tree problem.