{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:20:02Z","timestamp":1773656402805,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2013,1,19]],"date-time":"2013-01-19T00:00:00Z","timestamp":1358553600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s10107-013-0631-6","type":"journal-article","created":{"date-parts":[[2013,1,18]],"date-time":"2013-01-18T04:06:58Z","timestamp":1358482018000},"page":"247-264","source":"Crossref","is-referenced-by-count":8,"title":["Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem"],"prefix":"10.1007","volume":"144","author":[{"given":"Alejandro","family":"Toriello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,1,19]]},"reference":[{"key":"631_CR1","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1287\/msom.5.4.348.24884","volume":"5","author":"D Adelman","year":"2003","unstructured":"Adelman, D.: Price-directed replenishment of subsets: methodology and its application to inventory routing. Manuf. Serv. Oper. Manag. 5, 348\u2013371 (2003)","journal-title":"Manuf. Serv. Oper. Manag."},{"key":"631_CR2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1287\/opre.1040.0114","volume":"52","author":"D Adelman","year":"2004","unstructured":"Adelman, D.: A price-directed approach to stochastic inventory\/routing. Oper. Res. 52, 499\u2013514 (2004)","journal-title":"Oper. Res."},{"key":"631_CR3","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1287\/opre.1060.0368","volume":"55","author":"D Adelman","year":"2007","unstructured":"Adelman, D.: Dynamic bid prices in revenue management. Oper. Res. 55, 647\u2013661 (2007)","journal-title":"Oper. Res."},{"key":"631_CR4","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1287\/moor.1040.0109","volume":"30","author":"D Adelman","year":"2005","unstructured":"Adelman, D., Klabjan, D.: Duality and existence of optimal policies in generalized joint replenishment. Math. Oper. Res. 30, 28\u201350 (2005)","journal-title":"Math. Oper. Res."},{"key":"631_CR5","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1287\/ijoc.1100.0433","volume":"24","author":"D Adelman","year":"2011","unstructured":"Adelman, D., Klabjan, D.: Computing near-optimal policies in generalized joint replenishment. INFORMS J. Comput. 24, 148\u2013164 (2011)","journal-title":"INFORMS J. Comput."},{"key":"631_CR6","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1287\/opre.47.6.889","volume":"47","author":"D Adelman","year":"1999","unstructured":"Adelman, D., Nemhauser, G.L.: Price-directed control of remnant inventory systems. Oper. Res. 47, 889\u2013898 (1999)","journal-title":"Oper. Res."},{"key":"631_CR7","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"DL Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)"},{"key":"631_CR8","doi-asserted-by":"crossref","unstructured":"Arora, S.: Approximation Algorithms for Geometric TSP. In Gutin and Punnen [25], pp. 207\u2013222","DOI":"10.1007\/0-306-48213-4_5"},{"key":"631_CR9","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Oveis Gharan, S., Saberi, A.: An $$ O(\\log n\/\\log \\log n)$$ -approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 379\u2013389. SIAM (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"631_CR10","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1287\/ijoc.13.1.56.9748","volume":"13","author":"E Balas","year":"2001","unstructured":"Balas, E., Simonetti, N.: Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study. INFORMS J. Comput. 13, 56\u201375 (2001)","journal-title":"INFORMS J. Comput."},{"key":"631_CR11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. Assoc. Comput. Mach. 9, 61\u201363 (1962)","journal-title":"J. Assoc. Comput. Mach."},{"key":"631_CR12","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/s10107-004-0506-y","volume":"100","author":"R Carr","year":"2004","unstructured":"Carr, R., Vempala, S.: On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Math. Program. 100, 569\u2013587 (2004)","journal-title":"Math. Program."},{"key":"631_CR13","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/net.3230110207","volume":"11","author":"N Christofides","year":"1981","unstructured":"Christofides, N., Mingozzi, A., Toth, P.: State space relaxation procedures for the computation of bounds to routing problems. Networks 11, 145\u2013164 (1981)","journal-title":"Networks"},{"key":"631_CR14","unstructured":"Cvetkovi\u0107, D., Cangalovi\u0107, M., Kovac\u0306evi\u0107-Vujc\u0306i\u0107, V.: Semidefinite programming methods for the symmetric traveling salesman problem. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) Proceedings of the 7th International Integer Programming and Combinatorial Optimization (IPCO) Conference, Graz, Austria, June 9\u201311, 1999, pp. 126\u2013136 (1999)"},{"key":"631_CR15","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1287\/opre.51.6.850.24925","volume":"51","author":"DP Farias de","year":"2003","unstructured":"de Farias, D.P., van Roy, B.: The linear programming approach to approximate dynamic programming. Oper. Res. 51, 850\u2013865 (2003)","journal-title":"Oper. Res."},{"key":"631_CR16","doi-asserted-by":"crossref","first-page":"1559","DOI":"10.1137\/070711141","volume":"19","author":"E Klerk de","year":"2008","unstructured":"de Klerk, E., Pasechnik, D., Sotirov, R.: On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Optim. 19, 1559\u20131573 (2008)","journal-title":"SIAM J. Optim."},{"key":"631_CR17","unstructured":"Desai, V.V., Farias, V.F., Moallemi, C.C.: The smoothed approximate linear program. To appear in Operations Research. Preprint available online at arXiv:0908.0506v2 (2009)"},{"key":"631_CR18","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1287\/opre.43.2.367","volume":"43","author":"Y Dumas","year":"1995","unstructured":"Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.: An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43, 367\u2013371 (1995)","journal-title":"Oper. Res."},{"key":"631_CR19","first-page":"69","volume-title":"Combinatorial structures and their applications","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (eds.) Combinatorial structures and their applications, pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"631_CR20","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.disopt.2005.10.002","volume":"3","author":"\u00d6 Ergun","year":"2006","unstructured":"Ergun, \u00d6., Orlin, J.B.: A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem. Discret. Optim. 3, 78\u201385 (2006)","journal-title":"Discret. Optim."},{"key":"631_CR21","unstructured":"Farias, V.F., van Roy, B.: An Approximate Dynamic Programming Approach to Network Revenue Management. Preprint available online at http:\/\/web.mit.edu\/vivekf\/www\/mypapers2.html (2007)"},{"key":"631_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"AM Frieze","year":"1982","unstructured":"Frieze, A.M., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12, 23\u201339 (1982)","journal-title":"Networks"},{"key":"631_CR23","first-page":"335","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335\u2013349 (1995)","journal-title":"Math. Program."},{"key":"631_CR24","unstructured":"Gonzales, R.H.: Solution to the traveling salesman problem by dynamic programming on the hypercube. Technical Report 18, Operations Research Center, Massachusetts Institute of Technology (1962)"},{"key":"631_CR25","volume-title":"The Traveling Salesman Problem and Its Variations","year":"2002","unstructured":"Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and Its Variations. Kluwer, Dordrecht (2002)"},{"key":"631_CR26","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10, 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"631_CR27","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138\u20131162 (1970)","journal-title":"Oper. Res."},{"key":"631_CR28","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M Held","year":"1971","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees: part II. Math. Program. 1, 6\u201325 (1971)","journal-title":"Math. Program."},{"key":"631_CR29","unstructured":"Houck, D., Picard, J.C., Queyranne, M., Vemuganti, R.R.: The Traveling Salesman Problem and Shortest $$n$$ -paths. University of Maryland, Technical report (1977)"},{"key":"631_CR30","first-page":"1","volume-title":"Jahrbuch \u00dcberblicke Mathematik","author":"M J\u00fcnger","year":"1993","unstructured":"J\u00fcnger, M., Pulleyblank, W.R.: Geometric duality and combinatorial optimization. In: Chatterji, S.D., Fuchssteiner, B., Kulisch, U., Liedl, R. (eds.) Jahrbuch \u00dcberblicke Mathematik, pp. 1\u201324. Vieweg, Braunschweig (1993)"},{"key":"631_CR31","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0377-2217(95)00205-7","volume":"94","author":"H Lee","year":"1996","unstructured":"Lee, H., Nemhauser, G.L., Wang, Y.: Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case. Eur. J. Oper. Res. 94, 154\u2013166 (1996)","journal-title":"Eur. J. Oper. Res."},{"key":"631_CR32","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0377-2217(94)00299-1","volume":"30","author":"C Malandraki","year":"1996","unstructured":"Malandraki, C., Dial, R.B.: A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. Eur. J. Oper. Res. 30, 45\u201355 (1996)","journal-title":"Eur. J. Oper. Res."},{"key":"631_CR33","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1287\/opre.45.3.365","volume":"45","author":"A Mingozzi","year":"1997","unstructured":"Mingozzi, A., Bianco, L., Ricciardelli, S.: Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Oper. Res. 45, 365\u2013377 (1997)","journal-title":"Oper. Res."},{"key":"631_CR34","unstructured":"Nadarajah, S., Margot, F., Secomandi, N.: Approximate Dynamic Programs for Natural Gas Storage Valuation Based on Approximate Linear Programming Relaxations. Technical Report 2011\u2013E5, Tepper School of Business, Carnegie Mellon University (2011)"},{"key":"631_CR35","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1287\/trsc.14.2.130","volume":"14","author":"HN Psaraftis","year":"1980","unstructured":"Psaraftis, H.N.: A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transp. Sci. 14, 130\u2013154 (1980)","journal-title":"Transp. Sci."},{"key":"631_CR36","unstructured":"Schrijver, A.: The traveling salesman problem. In: Combinatorial Optimization: Polyhedra and Efficiency. vol. B, chapter 58, pp. 981\u20131004. Springer, Berlin (2003)"},{"key":"631_CR37","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/0022-247X(85)90317-8","volume":"110","author":"PJ Schweitzer","year":"1985","unstructured":"Schweitzer, P.J., Seidmann, A.: Generalized polynomial approximations in Markovian decision processes. J. Math. Anal. Appl. 110, 568\u2013582 (1985)","journal-title":"J. Math. Anal. Appl."},{"key":"631_CR38","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"DB Shmoys","year":"1990","unstructured":"Shmoys, D.B., Williamson, D.P.: Analyzing the Held-Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35, 281\u2013285 (1990)","journal-title":"Inf. Process. Lett."},{"key":"631_CR39","unstructured":"Trick, M.A., Zin, S.E.: A Linear Programming Approach to Solving Stochastic Dynamic Programs. Unpublished manuscript available online at http:\/\/mat.gsia.cmu.edu\/trick\/ (1993)"},{"key":"631_CR40","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1017\/S1365100597002095","volume":"1","author":"MA Trick","year":"1997","unstructured":"Trick, M.A., Zin, S.E.: Spline approximations to value functions: a linear programming approach. Macroecon. Dyn. 1, 255\u2013277 (1997)","journal-title":"Macroecon. Dyn."},{"key":"631_CR41","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s10107-005-0663-7","volume":"105","author":"M Vyve van","year":"2006","unstructured":"van Vyve, M., Wolsey, L.A.: Approximate extended formulations. Math. Program. 105, 501\u2013522 (2006)","journal-title":"Math. Program."},{"key":"631_CR42","unstructured":"Williamson, D.P.: Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem. Master\u2019s thesis, Massachusetts Institute of Technology (1989)"},{"key":"631_CR43","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"LA Wolsey","year":"1980","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13, 121\u2013134 (1980)","journal-title":"Math. Program. Study"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0631-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-013-0631-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0631-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T13:03:59Z","timestamp":1562591039000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-013-0631-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,19]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["631"],"URL":"https:\/\/doi.org\/10.1007\/s10107-013-0631-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,19]]}}}