An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem

An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem

We study an extension of the classical traveling salesman problem (TSP) to a situation with k≥2 depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2−1/k, which improves on the known 2-...

Full description

Saved in:
Bibliographic Details
Main Authors: XU, Zhou, XU, Liang, RODRIGUES, Brian Charles
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2011
Subjects:
Approximation algorithms
Christofides heuristic
Multiple depots
TSP
Operations and Supply Chain Management
Online Access:https://ink.library.smu.edu.sg/lkcsb_research/4920
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:We study an extension of the classical traveling salesman problem (TSP) to a situation with k≥2 depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2−1/k, which improves on the known 2-approximation algorithm from the literature.

Similar Items