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:
TSP
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
id sg-smu-ink.lkcsb_research-5919
record_format dspace
spelling sg-smu-ink.lkcsb_research-59192016-03-28T03:18:05Z An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem XU, Zhou XU, Liang RODRIGUES, Brian Charles 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. 2011-05-01T07:00:00Z text https://ink.library.smu.edu.sg/lkcsb_research/4920 info:doi/10.1016/j.orl.2011.03.002 Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University Approximation algorithms Christofides heuristic Multiple depots TSP Operations and Supply Chain Management
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Approximation algorithms
Christofides heuristic
Multiple depots
TSP
Operations and Supply Chain Management
spellingShingle Approximation algorithms
Christofides heuristic
Multiple depots
TSP
Operations and Supply Chain Management
XU, Zhou
XU, Liang
RODRIGUES, Brian Charles
An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
description 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.
format text
author XU, Zhou
XU, Liang
RODRIGUES, Brian Charles
author_facet XU, Zhou
XU, Liang
RODRIGUES, Brian Charles
author_sort XU, Zhou
title An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
title_short An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
title_full An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
title_fullStr An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
title_full_unstemmed An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
title_sort analysis of the extended christofides heuristic for the k-depot travelling salesman problem
publisher Institutional Knowledge at Singapore Management University
publishDate 2011
url https://ink.library.smu.edu.sg/lkcsb_research/4920
_version_ 1770572862236655616