Title

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

Publication Type

Journal Article

Publication Date

5-2011

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

Keywords

Approximation algorithms, Christofides heuristic, Multiple depots, TSP

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Operations Research Letters

Volume

39

Issue

3

First Page

218

Last Page

223

ISSN

0167-6377

Identifier

10.1016/j.orl.2011.03.002

Publisher

Elsevier

Additional URL

http://dx.doi.org/10.1016/j.orl.2011.03.002

This document is currently not available here.

Share

COinS