2017
A priori TSP in the scenario model
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/978-3-319-51741-4_15 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| Workshop on Approximation and Online Algorithms | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
van Ee, M., van Iersel, L., Janssen, T., & Sitters, R. (2017). A priori TSP in the scenario model. In WAOA 2016: Approximation and Online Algorithms (pp. 183–196). doi:10.1007/978-3-319-51741-4_15 |
|
