




















We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem (also called the traveling deliveryman or minimum latency problem). Given a metric $(V,d)$ with a root $r\in 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 non-uniform probabilities. Previously, such a result was only known for uniform probabilities.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。