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

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

Title of host publication | Approximation and Online Algorithms |

Subtitle of host publication | 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016, Revised Selected Papers |

Editors | Klaus Jansen, Monaldo Mastrolilli |

Place of Publication | Cham |

Publisher | Springer International Publishing |

Pages | 183-196 |

Number of pages | 14 |

ISBN (Electronic) | 9783319517414 |

ISBN (Print) | 9783319517407 |

DOIs | |

Publication status | Published - 2017 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 10138 |

ISSN (Print) | 0302-9743 |

### Bibliographical note

Proceedings title: Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected PapersPublisher: Springer

Place of publication: Berlin

Editors: K. Jansen, M. Mastrolilli

## Fingerprint

Dive into the research topics of 'A*priori*TSP in the Scenario Model'. Together they form a unique fingerprint.