A priori TSP in the Scenario Model

Martijn van Ee, Leo van Iersel, Teun Janssen, R.A. Sitters

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationApproximation and Online Algorithms
EditorsKlaus Jansen, Monaldo Mastrolilli
Place of PublicationCham
PublisherSpringer International Publishing
Pages183-196
Number of pages14
ISBN (Print)978-3-319-51741-4
Publication statusPublished - 2017

Fingerprint

Travelling salesman problems
Scenarios
Model
Expected Length
Minimum Spanning Tree
Approximation Algorithms
NP-complete problem
Minimise
Subset

Cite this

van Ee, M., van Iersel, L., Janssen, T., & Sitters, R. A. (2017). A priori TSP in the Scenario Model. In K. Jansen, & M. Mastrolilli (Eds.), Approximation and Online Algorithms (pp. 183-196). Cham: Springer International Publishing.
van Ee, Martijn ; van Iersel, Leo ; Janssen, Teun ; Sitters, R.A. / A priori TSP in the Scenario Model. Approximation and Online Algorithms. editor / Klaus Jansen ; Monaldo Mastrolilli. Cham : Springer International Publishing, 2017. pp. 183-196
@inproceedings{0311c6e3507a4b3eb8c495a6c6993127,
title = "A priori TSP in the Scenario Model",
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.",
author = "{van Ee}, Martijn and {van Iersel}, Leo and Teun Janssen and R.A. Sitters",
year = "2017",
language = "English",
isbn = "978-3-319-51741-4",
pages = "183--196",
editor = "Klaus Jansen and Monaldo Mastrolilli",
booktitle = "Approximation and Online Algorithms",
publisher = "Springer International Publishing",

}

van Ee, M, van Iersel, L, Janssen, T & Sitters, RA 2017, A priori TSP in the Scenario Model. in K Jansen & M Mastrolilli (eds), 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.

Approximation and Online Algorithms. ed. / Klaus Jansen; Monaldo Mastrolilli. Cham : Springer International Publishing, 2017. p. 183-196.

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-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 -

van Ee M, van Iersel L, Janssen T, Sitters RA. A priori TSP in the Scenario Model. In Jansen K, Mastrolilli M, editors, Approximation and Online Algorithms. Cham: Springer International Publishing. 2017. p. 183-196