The Traveling Firefighter Problem
share
We introduce the L_p Traveling Salesman Problem (L_p-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. We provide an approximation preserving polynomial-time reduction of L_p-TSP to the segmented-TSP Problem [Sitters '14] and further study the case of p = 2, which we term the Traveling Firefighter Problem (TFP), when the cost due to a delay in service is quadratic in time. We also study the all-norm-TSP problem [Golovin et al. '08], 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, and improve corresponding (in)approximability bounds on metric spaces.
READ FULL TEXT