Retour aux résultats
Articles (2021), Theoretical Computer Science, 877, pp. 74-89

Approximation of the Double Traveling Salesman Problem with multiple stacks

ALFANDARI Laurent , TOULOUSE Sophie

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. Lien vers l'article

ALFANDARI, L. and TOULOUSE, S. (2021). Approximation of the Double Traveling Salesman Problem with multiple stacks. Theoretical Computer Science, 877, pp. 74-89.