The Chinese deliveryman problem

Martijn van Ee, René Sitters*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We introduce the Chinese deliveryman problem where the goal of the deliveryman is to visit every house in his neighborhood such that the average time of arrival is minimized. We show that, in contrast to the well-known Chinese postman problem, the Chinese deliveryman problem is APX-hard in general and NP-hard for planar graphs. We give a simple 2-approximation for undirected graphs and a 4 / 3-approximation for 2-edge connected graphs. We observe that there is a PTAS for planar graphs and that depth first search is optimal for trees.

Original languageEnglish
Pages (from-to)341-356
Number of pages16
Journal4OR
Volume18
Issue number3
Early online date19 Oct 2019
DOIs
Publication statusPublished - Sep 2020

Keywords

  • Approximation algorithms
  • Chinese deliveryman problem
  • Chinese postman problem
  • Computational complexity
  • Graph search

Fingerprint

Dive into the research topics of 'The Chinese deliveryman problem'. Together they form a unique fingerprint.

Cite this