Année
2021
Auteurs
ALFANDARI Laurent, TOULOUSE Sophie
Abstract
Highlights: We study the approximation of the Double Traveling Salesman Problem with Multiple Stacks. We study the complexity of two important subproblems. We provide approximation results for both standard and differential approximation. Approximation results are derived from reductions to the TSP in the general case. Algorithms based on optimal matchings and completions are analyzed for the case with two stacks.
ALFANDARI, L. et TOULOUSE, S. (2021). Approximation of the Double Traveling Salesman Problem with multiple stacks. Theoretical Computer Science, 877, pp. 74-89.