Multi Purpose Routing: New Perspectives and Approximation Algorithms
Published in arXiv, 2022
Recommended citation: Majid Farhadi, Jai Moondra, Prasad Tetali, Alejandro Toriello. (2022). "Multi Purpose Routing: New Perspectives and Approximation Algorithms." arXiv. https://arxiv.org/abs/2208.04410
Abstract: The cost due to delay in services may be intrinsically different for various applications of vehicle routing such as medical emergencies, logistical operations, and ride-sharing. We study a fundamental generalization of the Traveling Salesman Problem, namely $L_p$ TSP, where the objective is to minimize an aggregated measure of the delay in services, quantified by the Minkowski $p$-norm of the delay vector. We present efficient combinatorial and Linear Programming algorithms for approximating $L_p$ TSP on general metrics. We provide several approximation algorithms for the $L_p$ TSP problem, including $4.27$ & $10.92$-approximation algorithms for single & multi vehicle $L_2$ TSP, called the Traveling Firefighter Problem. Among other contributions, we provide an $8$-approximation and a $1.78$ inapproximability for All-Norm TSP problem, addressing scenarios where one does not know the ideal cost function, or is seeking simultaneous approximation with respect to any cost function.