A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots

DOI10.1287/IJOC.2015.0650zbMATH Open1338.90358OpenAlexW1857333123MaRDI QIDQ2802244FDOQ2802244

Authors: Zhou Xu, Brian Rodrigues 

Publication date: 25 April 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2015.0650

Recommendations

• A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• Multi-depot multiple TSP: a polyhedral study and computational results
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An approximation algorithm for the three depots Hamiltonian path problem
• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Approximability of the multiple stack TSP
• A multi-depot travelling salesman problem and its iterative and integrated approaches

zbMATH Keywords

approximation algorithmmatroidtraveling salesmanmultiple depots

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• Approximation Algorithms for Some Postman Problems
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• A variation of the generalized assignment problem arising in the New Zealand dairy industry
• A tabu search heuristic for the multi-depot vehicle routing problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• A unified modeling and solution framework for vehicle routing and local search-based metaheuristics
• State-of-the art review-evolutionary algorithms for vehicle routing
• New assignment algorithms for the multi-depot vehicle routing problem
• Approximations for minimum and min-max vehicle routing problems
• Approximation algorithms for multiple terminal, Hamiltonian path problems

Cited In (19)

• A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints
• The multiple traveling salesman problem on spiders
• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
• Reducing Path TSP to TSP
• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• Improved approximation algorithms for multidepot capacitated vehicle routing
• Approximation algorithms for the \(k\)-depots Hamiltonian path problem
• A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem
• Approximations for the Steiner multicycle problem
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• Exact and heuristic algorithms for routing AGV on path with precedence constraints
• New approximation algorithms for the heterogeneous weighted delivery problem
• New approximation algorithms for the heterogeneous weighted delivery problem
• Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
• Multi-depot multiple TSP: a polyhedral study and computational results
• An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem

This page was built for publication: A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802244)