Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
no edit summary
== Title ==
Movement Repairman Problem
== Speaker ==
Reza Khani
== Abstract ==
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.
The MR problem is very general; we present additional results to show the connections of this problem to the other well studied problems. It turns out that Sum-MR is closely related to the Neighborhood TSP problems which are studied well in Euclidean Space. We give a constant-factor approximation algorithm for Sum-MR in Euclidean Space. An alternate objective in the MR problem is to minimize the maximum latency seen by the clients. We study the Max Movement Repairman (Max-MR) problem in which the goal is to minimize the time of serving the latest client. We also give a constant-factor approximation algorithm for the Max-MR problem in the case where all repairmen have the same speed.
Movement Repairman Problem
== Speaker ==
Reza Khani
== Abstract ==
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.
The MR problem is very general; we present additional results to show the connections of this problem to the other well studied problems. It turns out that Sum-MR is closely related to the Neighborhood TSP problems which are studied well in Euclidean Space. We give a constant-factor approximation algorithm for Sum-MR in Euclidean Space. An alternate objective in the MR problem is to minimize the maximum latency seen by the clients. We study the Max Movement Repairman (Max-MR) problem in which the goal is to minimize the time of serving the latest client. We also give a constant-factor approximation algorithm for the Max-MR problem in the case where all repairmen have the same speed.
