3-approximation algorithm for a two depot, heterogeneous traveling salesman problem

DOI10.1007/s11590-010-0256-0zbMath1259.90116MaRDI QIDQ691417

Sai Yadlapalli, Sivakumar Rathinam, Swaroop Darbha

Publication date: 30 November 2012

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-010-0256-0

zbMATH Keywords

traveling salesman problem; heterogeneous vehicle

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

New approximation algorithms for the heterogeneous weighted delivery problem, New approximation algorithms for the heterogeneous weighted delivery problem, A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem, The hierarchical traveling salesman problem, 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem, Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs, A general variable neighborhood search variants for the travelling salesman problem with draft limits, Heuristics for routing heterogeneous unmanned vehicles with fuel constraints, Approximation algorithms for solving the heterogeneous Chinese postman problem

Uses Software

• TSPLIB

Cites Work

• Survivable networks, linear programming relaxations and the parsimonious property
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• The ellipsoid method and its consequences in combinatorial optimization
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• \(\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 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item