The Chinese deliveryman problem

DOI10.1007/S10288-019-00420-2MaRDI QIDQ2025136zbMATH OpenOpenAlexWikidataFDO

Authors Martijn van Ee, René A. Sitters

Publication date 11 May 2021

Published in 4OR (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexityapproximation algorithmsChinese postman problemgraph searchChinese 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)

Recommendations

• Chinese postman problem over 50 years
• The delivery man problem on a tree network
• scientific article; zbMATH DE number 3880464
• Arc Routing Problems, Part I: The Chinese Postman Problem
• An approximation algorithm for solving the heterogeneous Chinese postman problem

Cites work

• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 2086925 (Why is no real title available?)
• scientific article; zbMATH DE number 2102754 (Why is no real title available?)
• Approximation Schemes for Minimum Latency Problems
• Asymmetric traveling salesman path and directed latency problems
• Euler, Mei-ko Kwan, Königsberg, and a Chinese postman
• Generalizations in the linear search problem
• Matching, Euler tours and the Chinese postman
• On the complexity of edge traversing
• Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Some simplified NP-complete graph problems
• Son of the linear search problem
• Star search -- a different show
• The Traveling Salesman Problem with Distances One and Two
• The delivery man problem on a tree network
• The minimum latency problem

Cited in

(2)

• The Delivery Man Problem and Cumulative Matroids
• The concrete delivery problem

This page was built for publication: The Chinese deliveryman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2025136)