Additional Results and Extensions for the paper "Probabilistic bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem”

11/20/2022
by   Moise Blanchard, et al.
0

This technical report provides additional results for the main paper “Probabilistic bounds on the k-Traveling Salesman Problem (k-TSP) and the Traveling Repairman Problem (TRP)”. For the k-TSP, we extend the probabilistic bounds derived in the main paper to the case of distributions with general densities. For the TRP, we propose a utility-based notion of fairness and derive constant-factor probabilistic bounds for this objective, thus extending the TRP bounds from the main paper to non-linear utilities.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset