TY - JOUR

T1 - A priori TSP in the scenario model

AU - van Ee, Martijn

AU - van Iersel, Leo

AU - Janssen, Teun

AU - Sitters, René

PY - 2018/12/11

Y1 - 2018/12/11

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

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

KW - a priori optimization

KW - Master tour

KW - Optimization under scenarios

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85046159723&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046159723&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.04.002

DO - 10.1016/j.dam.2018.04.002

M3 - Article

AN - SCOPUS:85046159723

VL - 250

SP - 331

EP - 341

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -