Routing under Uncertainty: the a priori Traveling Repairman Problem

M. van Ee, R.A. Sitters

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem (TSP), the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we give the first constant-factor approximation for a priori TRP.
Original languageEnglish
Pages (from-to)248-259
JournalLecture Notes in Computer Science
Volume8952
DOIs
Publication statusPublished - 2015
Event12th Workshop on Approximation and Online Algorithms - Berlin
Duration: 11 Sept 201412 Sept 2014

Bibliographical note

Proceedings title: Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers
Publisher: Springer
Place of publication: Berlin
Editors: E. Bampis, O. Svensson

Fingerprint

Dive into the research topics of 'Routing under Uncertainty: the a priori Traveling Repairman Problem'. Together they form a unique fingerprint.

Cite this