Exact and approximation algorithms for the min-max k-traveling salesmen problem on a tree

Liang Xu, Zhou Xu, Dongsheng Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

Given k identical salesmen, where k ≥ 2 is a constant independent of the input size, the min-max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ≥ 2, closing a question that has remained open for a decade. Along with this, we have further developed a 1 + -Approximation algorithm for any 0.
Original languageEnglish
Pages (from-to)284-292
Number of pages9
JournalEuropean Journal of Operational Research
Volume227
Issue number2
DOIs
Publication statusPublished - 1 Jun 2013

Keywords

  • Approximation algorithm
  • Exact algorithm
  • k-Traveling salesmen problem
  • Min-max
  • Tree

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this