| − | In the Movement Repairman (MR) problem we are given a metric space (V, d) along with a set R of k repairmen r_1, r_2, ..., r_k with their start depots s_1, s_2, ..., s_k \in V and speeds v_1, v_2, ..., v_k > 0 respectively and a set C of m clients c_1, c_2, ..., c_m having start locations s'_1, s'_2, ..., s'_m \in V and speeds v'_1, v'_2, ..., v'_m > 0 respectively. If t is the earliest time a client c_j is collocated with any repairman (say, r_i) at a node u, we say that the client is served by r_i at u and that its latency is t. The objective in the Sum Movement Repairman (Sum-MR) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients' latencies. We give the first O(\log n)-approximation algorithm for the Sum-MR problem. In order to do so we give a natural LP formulation for this problem and bound its integrality gap. In order to be able to solve the LP in polynomial time, we relax the LP allowing the repairmen and clients to travel a little more. We next round the relaxed LP using randomization applied to each of the geometrically increasing segments of the time line.
| |