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

The k-traveling salesman problem (k-TSP) seeks a tour of minimal length that visits a subset of k & LE; n points. The traveling repairman problem (TRP) seeks a complete tour with minimal latency. This paper provides constant-factor probabilistic approximations of both problems. We first show that the optimal length of the k-TSP path grows at a � rate of & UTheta; k/nk/(2(k �1))�. The proof provides a constant-factor approximation scheme, which solves a TSP in a high-concentration zone, leveraging large deviations of local concentrations. Then, we show that the optimal TRP latency grows at a rate of & UTheta;(n & RADIC;). This result ffififfi n extends the classic Beardwood-Halton-Hammersley theorem to the TRP. Again, the proof provides a constant-factor approximation scheme, which visits zones by decreasing order of probability density. We discuss practical implications of this result in the design of transportation and logistics systems. Finally, we propose dedicated notions of fairness- randomized population-based fairness for the k-TSP and geographic fairness for the TRP- and give algorithms to balance efficiency and fairness.

Automated summary

This paper provides constant-factor probabilistic approximations for both the k-traveling salesman problem (k-TSP) and traveling repairman problem (TRP). The optimal length of the k-TSP path grows at a rate of Θ(k/nk/(2(k-1))), and the optimal TRP latency grows at a rate of Θ(n√). The proof for both problems provides constant-factor approximation schemes and discusses practical implications in transportation and logistics systems. The paper also proposes dedicated notions of fairness for k-TSP and TRP, and algorithms to balance efficiency and fairness.