A priori TSP in the Scenario Model

Martijn van Ee, Leo van Iersel, Teun Janssen, René Sitters

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Citations (Scopus)

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
Subtitle of host publication14th International Workshop, WAOA 2016, Revised Selected Papers
EditorsKlaus Jansen, Monaldo Mastrolilli
Place of PublicationCham
PublisherSpringer
Pages183-196
Number of pages14
ISBN (Electronic)978-3-319-51741-4
ISBN (Print)978-3-319-51740-7
DOIs
Publication statusPublished - 2017
Event14th International Workshop on Approximation and Online Algorithms, WAOA 2016 - Aarhus, Denmark
Duration: 25 Aug 201626 Aug 2016
Conference number: 14

Publication series

NameLecture Notes in Computer Science
Volume10138
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop14th International Workshop on Approximation and Online Algorithms, WAOA 2016
Abbreviated titleWAOA
Country/TerritoryDenmark
CityAarhus
Period25/08/1626/08/16

Keywords

  • Traveling salesman problem
  • A priori optimization
  • Master tour
  • Optimization under scenarios

Fingerprint

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

Cite this