Approximation algorithms for the a priori traveling repairman

Fatemeh Navidi, Inge Li Gørtz, Viswanath Nagarajan*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem. Given a metric (V,d) with a root r∈V, the traveling repairman problem (TRP) involves finding a tour originating from r that minimizes the sum of arrival-times at all vertices. In its a priori version, we are also given independent probabilities of each vertex being active. We want to find a master tour τ originating from r and visiting all vertices. The objective is to minimize the expected sum of arrival-times at all active vertices, when τ is shortcut over the inactive vertices. We obtain the first constant-factor approximation algorithm for a priori TRP under independent non-uniform probabilities. Our result provides a general reduction from non-uniform to uniform probabilities, and uses (in black-box manner) an existing approximation algorithm for a priori TRP under uniform probabilities.

Original languageEnglish
JournalOperations Research Letters
Volume48
Issue number5
Pages (from-to)599-606
ISSN0167-6377
DOIs
Publication statusPublished - Sep 2020

Keywords

  • A priori optimization
  • Approximation algorithms
  • Traveling repairman problem

Fingerprint Dive into the research topics of 'Approximation algorithms for the a priori traveling repairman'. Together they form a unique fingerprint.

Cite this