Sharif Digital Repository

In a real-time routing problem, a sequence of requests emerge overtime in a metric and should be served by $k$ moving agents (i.e. the servers) in order to minimize a certain cost function. If the cost function is the average of completion time of the requests, the problem is named \textit{online $k$-traveling repairman problem}. An online algorithm with lookahead would be aware about next arising requests in a specific time-window. We present deterministic and randomized algorithms with competitive ratios $5.829-\delta$ and $3.873-\delta$ against and oblivious adversary, where $\delta$ depends on server's lookahead, specification of metric and last request's release time. We the show...