Online Service with Per-Batch Maximum Delays
Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting its requests' locations. Movement is instantaneous. The objective is to minimize the total distance traveled by the server plus the sum, over all batches, of the maximum waiting time in each batch. We give deterministic polynomial-time algorithms with competitive ratios $10$ on finite lines, $12$ on weighted trees, and $20$ on arbitrary finite metrics. Unlike additive delay, maximum delay allows younger requests to join a batch without increasing its delay charge. Our algorithms coordinate service using a common waiting clock and a threshold determined by the metric. The analysis uses certificates for groups of requests to compare this policy with any offline schedule, even one that serves different batches and follows different walks. This comparison shows that coordinating service in this way loses only a constant factor. The bounds hold whether the server must serve requests it visits or may leave them unserved; the two rules also have equal offline optimal costs. Offline optimization is polynomial on lines and explicitly represented weighted trees, and NP hard on general metrics. When arrivals are announced but locations are hidden until visited, we give an $84$-competitive algorithm on a known finite line under either rule.
尚无 AI 解读，展示原文摘要