The Chinese deliveryman problem

DOI10.1007/s10288-019-00420-2zbMath1468.90116OpenAlexW2981260297WikidataQ126992817 ScholiaQ126992817MaRDI QIDQ2025136

Martijn van Ee, R. A. Sitters

Publication date: 11 May 2021

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-019-00420-2

zbMATH Keywords

computational complexityapproximation algorithmsgraph searchChinese postman problemChinese deliveryman problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The delivery man problem on a tree network
• Some simplified NP-complete graph problems
• Star search -- a different show
• Generalizations in the linear search problem
• Euler, Mei-ko Kwan, Königsberg, and a Chinese postman
• Son of the linear search problem
• The minimum latency problem
• Asymmetric Traveling Salesman Path and Directed Latency Problems
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• On the complexity of edge traversing
• Approximation Schemes for Minimum Latency Problems
• The Traveling Salesman Problem with Distances One and Two
• Matching, Euler tours and the Chinese postman
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.

This page was built for publication: The Chinese deliveryman problem