A priori TSP in the Scenario Model

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

doi:10.1007/978-3-319-51741-4_15

A priori TSP in the Scenario Model

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

Amsterdam Business Research Institute

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

2 Downloads (Pure)

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	https://doi.org/10.1007/978-3-319-51741-4_15
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 Papers
Publisher: Springer
Place of publication: Berlin
Editors: K. Jansen, M. Mastrolilli

Access to Document

10.1007/978-3-319-51741-4_15

A priori TSP in the Scenario ModelFinal published version, 296 KBLicence: Article 25fa Dutch Copyright Act

Handle.net

Persistent link

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: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016, Revised Selected Papers (pp. 183-196). (Lecture Notes in Computer Science; Vol. 10138). Springer International Publishing. Advance online publication. https://doi.org/10.1007/978-3-319-51741-4_15

van Ee, Martijn ; van Iersel, Leo ; Janssen, Teun et al. / A priori TSP in the Scenario Model. Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016, Revised Selected Papers. editor / Klaus Jansen ; Monaldo Mastrolilli. Cham : Springer International Publishing, 2017. pp. 183-196 (Lecture Notes in Computer Science).

@inbook{a6905941fee14e57aba224f5b0673e0b,

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",

note = "Proceedings title: Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected Papers Publisher: Springer Place of publication: Berlin Editors: K. Jansen, M. Mastrolilli",

year = "2017",

doi = "10.1007/978-3-319-51741-4_15",

language = "English",

isbn = "9783319517407",

series = "Lecture Notes in Computer Science",

publisher = "Springer International Publishing",

pages = "183--196",

editor = "Klaus Jansen and Monaldo Mastrolilli",

booktitle = "Approximation and Online Algorithms",

}

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: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10138, Springer International Publishing, Cham, pp. 183-196. https://doi.org/10.1007/978-3-319-51741-4_15

A priori TSP in the Scenario Model. / van Ee, Martijn; van Iersel, Leo; Janssen, Teun et al.
Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016, Revised Selected Papers. ed. / Klaus Jansen; Monaldo Mastrolilli. Cham: Springer International Publishing, 2017. p. 183-196 (Lecture Notes in Computer Science; Vol. 10138).

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

TY - CHAP

T1 - A priori TSP in the Scenario Model

AU - van Ee, Martijn

AU - van Iersel, Leo

AU - Janssen, Teun

AU - Sitters, R.A.

N1 - Proceedings title: Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected Papers Publisher: Springer Place of publication: Berlin Editors: K. Jansen, M. Mastrolilli

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.

UR - http://www.scopus.com/inward/record.url?scp=85010671925&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010671925&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51741-4_15

DO - 10.1007/978-3-319-51741-4_15

M3 - Chapter

SN - 9783319517407

T3 - Lecture Notes in Computer Science

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: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016, Revised Selected Papers. Cham: Springer International Publishing. 2017. p. 183-196. (Lecture Notes in Computer Science). Epub 2017 Jan 7. doi: 10.1007/978-3-319-51741-4_15

A priori TSP in the Scenario Model

Abstract

Publication series

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this