{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T09:32:25Z","timestamp":1744709545498,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T00:00:00Z","timestamp":1571443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T00:00:00Z","timestamp":1571443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001833","name":"VU University Amsterdam","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001833","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\sqrt{2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msqrt><mml:mn>2<\/mml:mn><\/mml:msqrt><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for undirected graphs and a 4\u00a0\/\u00a03-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.<\/jats:p>","DOI":"10.1007\/s10288-019-00420-2","type":"journal-article","created":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T17:11:46Z","timestamp":1571505106000},"page":"341-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Chinese deliveryman problem"],"prefix":"10.1007","volume":"18","author":[{"given":"Martijn","family":"van Ee","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0385-0794","authenticated-orcid":false,"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,19]]},"reference":[{"key":"420_CR1","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1137\/S0097539701399654","volume":"32","author":"S Arora","year":"2003","unstructured":"Arora S, Karakostas G (2003) Approximation schemes for minimum latency problems. SIAM J Comput 32:1317\u20131337","journal-title":"SIAM J Comput"},{"key":"420_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Safra S (1998) Probabilistic checking of proofs: a new characterization of NP. J ACM 45:70\u2013122","journal-title":"J ACM"},{"key":"420_CR3","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998a) Proof verification and the hardness of approximation problems. J ACM 45:501\u2013555","journal-title":"J ACM"},{"key":"420_CR4","unstructured":"Arora S, Grigni M, Karger D, Klein P, Woloszyn A (1998b) A polynomial time approximation scheme for weighted planar graph TSP. In: 9th ACM\u2013SIAM symposium on discrete algorithms, pp 33\u201341"},{"key":"420_CR5","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF02783218","volume":"90","author":"V Baston","year":"1995","unstructured":"Baston V, Beck A (1995) Generalizations in the linear search problem. Israel J Math 90:301\u2013323","journal-title":"Israel J Math"},{"key":"420_CR6","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02761156","volume":"48","author":"A Beck","year":"1984","unstructured":"Beck A, Beck M (1984) Son of the linear search problem. Israel J Math 48:109\u2013122","journal-title":"Israel J Math"},{"key":"420_CR7","doi-asserted-by":"crossref","unstructured":"Blum A, Chalasani P, Coppersmith D, Pulleyblank W, Raghavan P, Sudan M (1994) The minimum latency problem. In: Proceedings of 26th ACM symposium on theory of computing, Montreal, Quebec, Canada, pp 163\u2013171","DOI":"10.1145\/195058.195125"},{"key":"420_CR8","doi-asserted-by":"publisher","first-page":"1511","DOI":"10.1007\/978-1-4419-7997-1_76","volume-title":"Handbook of combinatorial optimization","author":"A Bonato","year":"2013","unstructured":"Bonato A, Yang B (2013) Graph searching and related problems. In: Pardalos PM, Du DZ, Graham RL (eds) Handbook of combinatorial optimization. Springer, New York, pp 1511\u20131558"},{"key":"420_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhuri K, Godfrey B, Rao S, Talwar K (2003) Paths, trees, and minimum latency tours. In: Proceedings of 44nd symposium foundations of computer science, Cambridge, MA, pp 36\u201345","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"420_CR10","first-page":"73","volume":"13","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) The Chinese postman problem. Oper Res 13:73\u201377","journal-title":"Oper Res"},{"key":"420_CR11","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds J, Johnson E (1973) Matchings, Euler tours and the Chinese postman. Math Program 5:88\u2013124","journal-title":"Math Program"},{"key":"420_CR12","doi-asserted-by":"publisher","first-page":"1596","DOI":"10.1137\/100797357","volume":"42","author":"Z Friggstad","year":"2013","unstructured":"Friggstad Z, Salavatipour MR, Svitkina Z (2013) Asymmetric traveling salesman path and directed latency problems. SIAM J Comput 42:1596\u20131619","journal-title":"SIAM J Comput"},{"key":"420_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey M, Johnson D, Stockmeyer L (1976) Some simplified NP-complete problems. Theor Comput Sci 1:237\u2013267","journal-title":"Theor Comput Sci"},{"key":"420_CR14","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M, Yuan Y (2012) Euler, Mei-Ko Kwan, K\u00f6nigsberg, and a Chinese postman. Doc Math 43\u201350","DOI":"10.4171\/dms\/6\/10"},{"key":"420_CR15","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02761302","volume":"81","author":"O Kella","year":"1993","unstructured":"Kella O (1993) Star search\u2014a different show. Israel J Math 81:145\u2013159","journal-title":"Israel J Math"},{"key":"420_CR16","doi-asserted-by":"crossref","unstructured":"Koutsoupias E, Papadimitriou C, Yannakakis M (1996) Searching a fixed graph. In: Proceedings of 23rd international colloquium on automata, languages, and programming, LNCS, vol 1099, Paderborn, Germany, Springer, pp 280\u2013289","DOI":"10.1007\/3-540-61440-0_135"},{"key":"420_CR17","first-page":"263","volume":"10","author":"MK Kwan","year":"1960","unstructured":"Kwan MK (1960) Programming method using odd or even points. Acta Math Sin 10:263\u2013266 In Chinese","journal-title":"Acta Math Sin"},{"key":"420_CR18","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02097807","volume":"18","author":"E Minieka","year":"1989","unstructured":"Minieka E (1989) The delivery man problem on a tree network. Ann Oper Res 18:261\u2013266","journal-title":"Ann Oper Res"},{"key":"420_CR19","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1145\/321958.321974","volume":"23","author":"C Papadimitriou","year":"1976","unstructured":"Papadimitriou C (1976) On the complexity of edge traversing. J ACM 23:544\u2013554","journal-title":"J ACM"},{"key":"420_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C Papadimitriou","year":"1993","unstructured":"Papadimitriou C, Yannakakis M (1993) The traveling salesman problem with distances one and two. Math Oper Res 18:1\u201311","journal-title":"Math Oper Res"},{"key":"420_CR21","doi-asserted-by":"crossref","unstructured":"Petersen J (1891) Die theorie der regul\u00e4ren graphen. Acta Math 193\u2013220","DOI":"10.1007\/BF02392606"},{"key":"420_CR22","doi-asserted-by":"crossref","unstructured":"Sitters R (2002) The minimum latency problem is NP-hard for weighted trees. In: Cook WJ, Schulz A (eds) Proceedings 9th international conference on integer programming and combinatorial optimization, LNCS, vol 2337. Springer, pp 230\u2013239","DOI":"10.1007\/3-540-47867-1_17"},{"key":"420_CR23","unstructured":"Sitters R (2019) Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. Technical report"},{"key":"420_CR24","unstructured":"van Ee M (2017) Routing under uncertainty: approximation and complexity. Ph.D. thesis, Vrije Universiteit Amsterdam"},{"key":"420_CR25","unstructured":"van Omme N (2011) Le probl\u00e8me du postier chinois cumulatif. Ph.D. thesis, University of Montreal"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-019-00420-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10288-019-00420-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-019-00420-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T21:55:07Z","timestamp":1695333307000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10288-019-00420-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,19]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["420"],"URL":"https:\/\/doi.org\/10.1007\/s10288-019-00420-2","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2019,10,19]]},"assertion":[{"value":"1 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}