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

Original language | English |
---|---|

Pages (from-to) | 331-341 |

Number of pages | 11 |

Journal | Discrete Applied Mathematics |

Volume | 250 |

Early online date | 16 Aug 2018 |

DOIs | |

Publication status | Published - 11 Dec 2018 |

### Funding

We would like to thank Karen Aardal, Jan Driessen and Neil Olver for useful discussions. A part of the work by Teun Janssen has been performed in the project INTEGRATE “Integrated Solutions for Agile Manufacturing in High-mix Semiconductor Fabs”, co-funded by grants from France, Italy, Ireland, The Netherlands and the ECSEL Joint Undertaking. Martijn van Ee and René Sitters are supported by the NWO Grant 612.001.215 . Leo van Iersel was partially supported by the NWO , including Vidi grant 639.072.602 , and partially by the 4TU Applied Mathematics Institute .

Funders | Funder number |
---|---|

4TU Applied Mathematics Institute | |

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 612.001.215, 639.072.602 |

Electronic Components and Systems for European Leadership |

## Keywords

- a priori optimization
- Master tour
- Optimization under scenarios
- Traveling salesman problem