Probabilistic Bounds on the k -Traveling Salesman Problem and the Traveling Repairman Problem.

This article focuses on providing constant-factor probabilistic approximations for two extensions of the traveling salesman problem (TSP): the k-traveling salesman problem (k-TSP), which seeks a minimal-length tour visiting a subset of k ≤ n points, and the traveling repairman problem (TRP), which seeks a complete tour minimizing total latency (sum of waiting times). It establishes that the optimal k-TSP tour length grows at a rate of Θ((k / n^{k/(2(k−1))})) and the optimal TRP latency grows at a rate of Θ(n√n), extending classical TSP results to these problems. The authors propose constructive approximation algorithms leveraging local point concentrations for k-TSP and zone-based tours ordered by decreasing density for TRP, and introduce fairness notions—randomized population-based fairness for k-TSP and geographic fairness for TRP—to address spatial discrimination inherent in these problems, analyzing the trade-offs between efficiency and fairness. These findings have practical implications for transportation and logistics systems where minimizing customer wait times is critical.