Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems
share
Multiple TSP (mTSP) is a important variant of TSP where a set of k salesperson together visit a set of n cities. The mTSP problem has applications to many real life applications such as vehicle routing. Rothkopf introduced another variant of TSP called many-visits TSP (MVTSP) where a request r(v)∈ℤ_+ is given for each city v and a single salesperson needs to visit each city r(v) times and return back to his starting point. A combination of mTSP and MVTSP called many-visits multiple TSP (MVmTSP) was studied by Bérczi, Mnich, and Vincze where the authors give approximation algorithms for various variants of MVmTSP. In this work, we show a simple linear programming (LP) based reduction that converts a mTSP LP-based algorithm to a LP-based algorithm for MVmTSP with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the MVmTSP. Our reduction shows that the addition of visit requests r(v) to mTSP does not make the problem harder to approximate even when r(v) is exponential in number of vertices. To apply our reduction, we either use existing LP-based algorithms for mTSP variants or show that several existing combinatorial algorithms for mTSP variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms as well achieving the improved guarantees.
READ FULL TEXT