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-...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2011
|
Subjects: | |
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 |