An analysis of the extended Christofides heuristic for the k-depot TSP

Zhou Xu; Liang Xu; Brian Rodrigues

doi:10.1016/j.orl.2011.03.002

An analysis of the extended Christofides heuristic for the k-depot TSP

Zhou Xu, Liang Xu, Brian Rodrigues

Research output: Journal article publication › Journal article › Academic research › peer-review

27 Citations (Scopus)

Abstract

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-1k, which improves on the known 2-approximation algorithm from the literature.

Original language	English
Pages (from-to)	218-223
Number of pages	6
Journal	Operations Research Letters
Volume	39
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2011.03.002
Publication status	Published - 1 May 2011

Keywords

Approximation algorithms
Christofides heuristic
Multiple depots
TSP

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

More information

10.1016/j.orl.2011.03.002

Cite this

@article{646a28db04c047358ddea53810fed2c8,

title = "An analysis of the extended Christofides heuristic for the k-depot TSP",

abstract = "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-1k, which improves on the known 2-approximation algorithm from the literature.",

keywords = "Approximation algorithms, Christofides heuristic, Multiple depots, TSP",

author = "Zhou Xu and Liang Xu and Brian Rodrigues",

year = "2011",

month = may,

day = "1",

doi = "10.1016/j.orl.2011.03.002",

language = "English",

volume = "39",

pages = "218--223",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - An analysis of the extended Christofides heuristic for the k-depot TSP

AU - Xu, Zhou

AU - Xu, Liang

AU - Rodrigues, Brian

PY - 2011/5/1

Y1 - 2011/5/1

N2 - 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-1k, which improves on the known 2-approximation algorithm from the literature.

AB - 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-1k, which improves on the known 2-approximation algorithm from the literature.

KW - Approximation algorithms

KW - Christofides heuristic

KW - Multiple depots

KW - TSP

UR - https://www.scopus.com/pages/publications/79956144068

U2 - 10.1016/j.orl.2011.03.002

DO - 10.1016/j.orl.2011.03.002

M3 - Journal article

SN - 0167-6377

VL - 39

SP - 218

EP - 223

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

An analysis of the extended Christofides heuristic for the k-depot TSP

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this