Approximating the k-traveling repairman problem with repairtimes

Given an undirected graph G=(V,E)G=(V,E) and a source vertex s∈Vs∈V, the k-traveling repairman (KTR) problem, also known as the minimum latency problem, asks for k tours, each starting at s and together covering all the vertices (customers) such that the sum of the latencies experienced by the customers is minimum. The latency of a customer p is defined to be the distance traveled (time elapsed) before visiting p for the first time. Previous literature on the KTR problem has considered the version of the problem in which the repairtime of a customer is assumed to be zero for latency calculations. We consider a generalization of the problem in which each customer has an associated repairtime. For a fixed k  , we present a (β+2)(β+2)-approximation algorithm for this problem, where β   is the best achievable approximation ratio for the KTR problem with zero repairtimes (currently β=6β=6). For arbitrary k  , we obtain a (32β+12)-approximation ratio. When the repairtimes of the customers are all the same, we present an approximation algorithm with a better ratio.2 We also introduce the bounded-latency problem, a complementary version of the KTR problem, in which we are given a latency bound L and are asked to find the minimum number of repairmen required to service all the customers such that the latency of no customer is more than L  . For this problem, we present a simple bicriteria approximation algorithm that finds a solution with at most 2/ρ2/ρ times the number of repairmen required by an optimal solution, with the latency of no customer exceeding (1+ρ)L(1+ρ)L, ρ>0ρ>0.