Abstract | ||
---|---|---|
In this paper, we consider the a priori traveling salesman problem (TSP) 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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-319-51741-4_15 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
Traveling salesman problem,A priori optimization,Master tour,Optimization under scenarios | Journal | 10138 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martijn van Ee | 1 | 4 | 3.45 |
Leo van Iersel | 2 | 215 | 24.58 |
Teun Janssen | 3 | 0 | 0.34 |
René Sitters | 4 | 261 | 21.88 |