The Traveling Firefighter Problem

Majid Farhadi, Alejandro Toriello, Prasad Tetali

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 = \infty$ 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.

Knowledge Graph



Sign up or login to leave a comment