The Traveling Firefighter Problem
Majid Farhadi, Alejandro Toriello, Prasad Tetali · Society for Industrial and Applied Mathematics eBooks · 2021
We introduce the Lp Traveling Salesman Problem (Lp-TSP), given by an origin, a set of destinations, and underlying distances. The objective is to schedule a destination visit sequence for a traveler of unit speed to minimize the Minkowski p-norm of the resulting vector of visit/service times. For p = ∞ the problem becomes a path variant of the TSP, and for p = 1 it defines the Traveling Repairman Problem (TRP), both at the center of classical combinatorial optimization. Lp-TSP can be formulated as a convex mixed-integer program and enables a smooth interpolation between path-TSP and TRP, corresponding to optimal routes from the perspective of a server versus the customers, respectively. The parameter p can affect fairness or efficiency of the solution: The case p = 2, which we term the Traveling Firefighter Problem (TFP), models the scenario when the cost/damage due to a delay in service is quadratic in time. We provide a polynomial-time reduction of Lp-TSP (losing a factor of 1 + ∊ in performance) to the segmented-TSP, a routing problem that defines a constant O(1 + ∊−2) number of deadlines by which given numbers of vertices should be visited. Subsequently we derive polynomial-time approximation schemes for Lp-TSP in the Euclidean metric and the tree metric (for which the problem is strongly NP-hard). We also study the all-norm-TSP, in which the objective is to find a route that is (approximately) optimal with respect to the minimization of any norm of the visit times. We improve the approximation bound for this problem to 8, down from 16, and further prove an impossibility for an approximation factor better than 1.78, even in line metrics. Finally, we show the performance of our algorithm can be optimized for a specific norm, particularly yielding a 5.65-approximation for the TFP on general metrics. We leave open several interesting directions to further develop this line of research.