A priori TSP in the scenario model

A priori TSP in the scenario model

van Ee, Martijn (Vrije Universiteit Amsterdam)
van Iersel, L.J.J. (TU Delft Discrete Mathematics and Optimization)
Janssen, T.M.L. (TU Delft Discrete Mathematics and Optimization)
Sitters, René (Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI))

2018-12-11

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.

a priori optimization
Master tour
Optimization under scenarios
Traveling salesman problem

http://resolver.tudelft.nl/uuid:fe4d93cd-7370-4433-b96c-585c2688627a

https://doi.org/10.1016/j.dam.2018.04.002

2019-02-16

0166-218X

Discrete Applied Mathematics, 250, 331-341

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

journal article

© 2018 Martijn van Ee, L.J.J. van Iersel, T.M.L. Janssen, René Sitters