{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:42:16Z","timestamp":1771623736433,"version":"3.50.1"},"reference-count":29,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1999,5,1]],"date-time":"1999-05-01T00:00:00Z","timestamp":925516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["European Journal of Operational Research"],"published-print":{"date-parts":[[1999,5]]},"DOI":"10.1016\/s0377-2217(98)00175-1","type":"journal-article","created":{"date-parts":[[2003,4,5]],"date-time":"2003-04-05T00:21:01Z","timestamp":1049502061000},"page":"489-508","source":"Crossref","is-referenced-by-count":10,"title":["Submodularity and the traveling salesman problem"],"prefix":"10.1016","volume":"114","author":[{"given":"Yale T.","family":"Herer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0377-2217(98)00175-1_BIB1","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1287\/mnsc.36.1.92","article-title":"One warehouse multiple retailer systems with vehicle routing costs","volume":"36","author":"Anily","year":"1990","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB2","doi-asserted-by":"crossref","unstructured":"Arora, S., 1996. Polynomial time approximation schemes for euclidean TSP and other geometric problems. Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS 96), pp. 2\u201312","DOI":"10.1109\/SFCS.1996.548458"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB3","unstructured":"Balas, E., Toth, P., 1985. Branch and bound methods. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (Eds.), The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization, Wiley, Chichester"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB4","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0377-2217(93)90266-P","article-title":"The multi-level uncapacitated facility location problem is not submodular","volume":"71","author":"Barros","year":"1993","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB5","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","article-title":"The shortest path through many points","volume":"55","author":"Beardwood","year":"1959","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"10.1016\/S0377-2217(98)00175-1_BIB6","unstructured":"Christofides, N., 1976. Worst-case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01582008","article-title":"The traveling salesman problem on a graph and some related integer polyhedra","volume":"33","author":"Cornu\u00e9jols","year":"1985","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB8","unstructured":"Eastman, W.L., 1958. Linear programming with pattern constraints. Ph.D. Dissertation, Harvard University, Boston, MA"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB9","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., 1987. Algorithms in Combinatorial Geometry. In: Brauer, W., Rozenberg, G., Salomaa, A. (Eds.), Springer, Berlin","DOI":"10.1007\/978-3-642-61568-9"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB10","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1287\/moor.17.4.951","article-title":"Simple power of two policies are close to optimal in a general class of production\/distribution networks with general joint setup costs","volume":"17","author":"Federgruen","year":"1992","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB11","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1112\/S0025579300000784","article-title":"The shortest path and the shortest road through n points","volume":"2","author":"Few","year":"1955","journal-title":"Mathematika"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1287\/opre.4.1.61","article-title":"The traveling-salesman problem","volume":"4","author":"Flood","year":"1956","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","article-title":"Outline of an algorithm for integer solutions to linear programs","volume":"64","author":"Gomory","year":"1958","journal-title":"Bull. Amer. Math. Soc."},{"key":"10.1016\/S0377-2217(98)00175-1_BIB14","unstructured":"Granot, G., Granot, F., Zhu, W.R., 1996. Naturally submodular digraphs and forbidden digraphs configurations. Working paper, Faculty of Commerce, University of British Columbia, Vancouver, B.C"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB15","unstructured":"Granot, D., Hamers, H., Tijs, S., 1997. On some balanced, totally balanced and submodular delivery games. Working paper, Faculty of Commerce, University of British Columbia, Vancouver, B.C"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB16","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1287\/moor.10.4.527","article-title":"Bounds and heuristics for capacitated routing problems","volume":"10","author":"Haimovich","year":"1985","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB17","unstructured":"Harris, F., 1915. Operations and Cost, (Factory Management Series), A.W. Shaw, Chicago, pp. 48\u201353"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB18","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB19","first-page":"673","article-title":"Naturally submodular graphs: A polynomially solvable class for the TSP","volume":"123","author":"Herer","year":"1993","journal-title":"The proceedings of the AMS"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB20","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/opre.45.1.102","article-title":"Heuristics for a one warehouse multi-retailer distribution problem with performance bounds","volume":"45","author":"Herer","year":"1997","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB21","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1018928911513","article-title":"Vehicle scheduling on a tree with release and handling times","volume":"69","author":"Karuno","year":"1997","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB22","doi-asserted-by":"crossref","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (Eds.), 1985. The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization. Wiley, Chichester","DOI":"10.1057\/jors.1986.117"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB23","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B., 1998. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, in press","DOI":"10.1137\/S0097539796309764"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB24","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An analysis of approximations for maximizing submodular set functions\u2013I","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB25","unstructured":"Padberg, M.W., Gr\u00f6tschel, M., 1985. Polyhedral computations. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (Eds.), The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization, Wiley, Chichester"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB26","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1145\/76359.76361","article-title":"Spacefilling curves and the planar traveling salesman problem","volume":"36","author":"Platzman","year":"1989","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB27","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","article-title":"An analysis of several heuristics for the traveling salesman problem","volume":"6","author":"Rosenkrantz","year":"1977","journal-title":"Siam Journal on Computing"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB28","doi-asserted-by":"crossref","first-page":"1416","DOI":"10.1287\/mnsc.31.11.1416","article-title":"98%-effective integer-ratio lot-sizing for one-warehouse multi-retailer systems","volume":"31","author":"Roundy","year":"1985","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(98)00175-1_BIB29","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/moor.11.4.699","article-title":"A 98%-effective lot-sizing rule for a multi-product, multi-stage production\/inventory system","volume":"11","author":"Roundy","year":"1986","journal-title":"Mathematics of Operations Research"}],"container-title":["European Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221798001751?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221798001751?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T06:07:51Z","timestamp":1578636471000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0377221798001751"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,5]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1999,5]]}},"alternative-id":["S0377221798001751"],"URL":"https:\/\/doi.org\/10.1016\/s0377-2217(98)00175-1","relation":{},"ISSN":["0377-2217"],"issn-type":[{"value":"0377-2217","type":"print"}],"subject":[],"published":{"date-parts":[[1999,5]]}}}