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.
Original language | English |
---|---|
Title of host publication | Approximation and Online Algorithms |
Subtitle of host publication | 14th International Workshop, WAOA 2016, Revised Selected Papers |
Editors | Klaus Jansen, Monaldo Mastrolilli |
Place of Publication | Cham |
Publisher | Springer |
Pages | 183-196 |
Number of pages | 14 |
ISBN (Electronic) | 978-3-319-51741-4 |
ISBN (Print) | 978-3-319-51740-7 |
DOIs | |
Publication status | Published - 2017 |
Event | 14th International Workshop on Approximation and Online Algorithms, WAOA 2016 - Aarhus, Denmark Duration: 25 Aug 2016 → 26 Aug 2016 Conference number: 14 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 10138 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Workshop
Workshop | 14th International Workshop on Approximation and Online Algorithms, WAOA 2016 |
---|---|
Abbreviated title | WAOA |
Country/Territory | Denmark |
City | Aarhus |
Period | 25/08/16 → 26/08/16 |
Keywords
- Traveling salesman problem
- A priori optimization
- Master tour
- Optimization under scenarios