A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem

DOI10.1007/S11590-015-0924-1zbMath1353.90126OpenAlexW938223372MaRDI QIDQ315496

Sivakumar Rathinam, Jungyun Bae

Publication date: 21 September 2016

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

Full work available at URL: https://doi.org/10.1007/s11590-015-0924-1

zbMATH Keywords

primal-dual methodtraveling salesman problemapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (2)

A note on primal-dual stability in infinite linear programming ⋮ Approximation algorithms for solving the heterogeneous Chinese postman problem

Cites Work

• Unnamed Item
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• Optimal paths for a car that goes both forwards and backwards
• \(\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
• Capacitated Vehicle Routing with Non-uniform Speeds
• A General Approximation Technique for Constrained Forest Problems

This page was built for publication: A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem