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 -