{"id":"arxiv/2611.15425","url":"https://arxiv.org/abs/2611.15425","tags":["cs.DS","math.CO"],"score":0,"title":"A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension","domain":"cs.DS","source":"arxiv","authors":["Daniel Skachkov","Yuriy Dorn"],"reviews":0,"subject":"cs.DS","summary":"In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}