A priori TSP in the Scenario Model

Conference paper (2017)

Authors

Martijn van Ee Vrije Universiteit Amsterdam
L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
T.M.L. Janssen Discrete Mathematics and Optimization - EEMCS
René Sitters Vrije Universiteit Amsterdam
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2017

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.

Files

Ee2017_Chapter_APrioriTSPInThe... (.pdf)
(.pdf | 0.372 Mb)

Download not available