A priori TSP in the scenario model

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

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

147 Downloads (Pure)

Abstract

In this paper, we consider the a priori traveling salesman problem 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
Pages (from-to)331-341
Number of pages11
JournalDiscrete Applied Mathematics
Volume250
Early online date16 Aug 2018
DOIs
Publication statusPublished - 11 Dec 2018

Funding

We would like to thank Karen Aardal, Jan Driessen and Neil Olver for useful discussions. A part of the work by Teun Janssen has been performed in the project INTEGRATE “Integrated Solutions for Agile Manufacturing in High-mix Semiconductor Fabs”, co-funded by grants from France, Italy, Ireland, The Netherlands and the ECSEL Joint Undertaking. Martijn van Ee and René Sitters are supported by the NWO Grant 612.001.215 . Leo van Iersel was partially supported by the NWO , including Vidi grant 639.072.602 , and partially by the 4TU Applied Mathematics Institute .

FundersFunder number
4TU Applied Mathematics Institute
Nederlandse Organisatie voor Wetenschappelijk Onderzoek612.001.215, 639.072.602
Electronic Components and Systems for European Leadership

    Keywords

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

    Fingerprint

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

    Cite this