### Abstract

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

Title of host publication | Approximation and Online Algorithms |

Editors | Klaus Jansen, Monaldo Mastrolilli |

Place of Publication | Cham |

Publisher | Springer International Publishing |

Pages | 183-196 |

Number of pages | 14 |

ISBN (Print) | 978-3-319-51741-4 |

Publication status | Published - 2017 |

### Fingerprint

### Cite this

*Approximation and Online Algorithms*(pp. 183-196). Cham: Springer International Publishing.

}

*Approximation and Online Algorithms.*Springer International Publishing, Cham, pp. 183-196.

**A priori TSP in the Scenario Model.** / van Ee, Martijn; van Iersel, Leo; Janssen, Teun; Sitters, R.A.

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A priori TSP in the Scenario Model

AU - van Ee, Martijn

AU - van Iersel, Leo

AU - Janssen, Teun

AU - Sitters, R.A.

PY - 2017

Y1 - 2017

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

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

M3 - Conference contribution

SN - 978-3-319-51741-4

SP - 183

EP - 196

BT - Approximation and Online Algorithms

A2 - Jansen, Klaus

A2 - Mastrolilli, Monaldo

PB - Springer International Publishing

CY - Cham

ER -