Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximation Algorithms for the A Priori TravelingRepairman   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 $\tau$ originating from $r$
and visiting all vertices. The objective is to minimize the expected sum of
arrival-times at all active vertices, when $\tau$ 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.

0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
23
The categories of this paper are: solv-int
18
The categories of this paper are: econ
35
The categories of this paper are: mtrl-th
16
The categories of this paper are: stat
2
The categories of this paper are: math
10
The categories of this paper are: q-bio
34
The categories of this paper are: chem-ph
20
The categories of this paper are: acc-phys
13
The categories of this paper are: quant-ph
12
The categories of this paper are: nucl-th
37
The categories of this paper are: supr-con
31
The categories of this paper are: ao-sci
29
The categories of this paper are: funct-an
26
The categories of this paper are: bayes-an