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 language | English |
---|---|
Pages (from-to) | 341-356 |
Number of pages | 16 |
Journal | 4OR |
Volume | 18 |
Issue number | 3 |
Early online date | 19 Oct 2019 |
DOIs | |
Publication status | Published - Sept 2020 |
Keywords
- Approximation algorithms
- Chinese deliveryman problem
- Chinese postman problem
- Computational complexity
- Graph search