A priori TSP in the scenario model

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

doi:10.1016/j.dam.2018.04.002

A priori TSP in the scenario model

Journal article (2018)

Authors

Martijn van Ee Vrije Universiteit Amsterdam

L.J.J. van Iersel Discrete Mathematics and Optimization -

T.M.L. Janssen Discrete Mathematics and Optimization -

René Sitters Centrum Wiskunde & Informatica (CWI), Vrije Universiteit Amsterdam

Research Group

Discrete Mathematics and Optimization () (TU Delft)

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

A priori optimization Master tour Optimization under scenarios Traveling salesman problem

To reference this document use:

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

More Info

expand_more

Published Date

11-12-2018

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 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

A_priori_tsp_postprint.pdf

(pdf | 0.436 Mb)

Unknown license

Download not available

1_s2.0_S0166218X18301975_main.... (pdf)

(pdf | 0.534 Mb)

- Embargo expired in 16-02-2019

Unknown license