An improved approximation algorithm for the clustered traveling salesman problem

DOI10.1016/j.ipl.2012.08.020zbMath1248.68551OpenAlexW1978707544MaRDI QIDQ456175

Xiaoguang Bao, Zhaohui Liu

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.08.020

zbMATH Keywords

approximation algorithmtraveling salesman problemclustered traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

On the minimum routing cost clustered tree problem ⋮ A note on approximation algorithms of the clustered traveling salesman problem ⋮ Picker Routing in AGV-Assisted Order Picking Systems ⋮ Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ On the Clustered Steiner Tree Problem ⋮ On the clustered Steiner tree problem

Cites Work

• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Combinatorial optimization. Theory and applications.
• Approximation Algorithms for Some Postman Problems

This page was built for publication: An improved approximation algorithm for the clustered traveling salesman problem