{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:21:20Z","timestamp":1772554880142,"version":"3.50.1"},"publisher-location":"Cham","reference-count":90,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319919072","type":"print"},{"value":"9783319919089","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Research in combinatorial optimization successfully combines diverse ideas drawn from computer science, mathematics, and operations research. We give a tour of this work, focusing on the early development of the subject and the central role played by linear programming. The paper concludes with a short wish list of future research directions.<\/jats:p>","DOI":"10.1007\/978-3-319-91908-9_3","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T09:05:00Z","timestamp":1570179900000},"page":"27-47","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Computing in Combinatorial Optimization"],"prefix":"10.1007","author":[{"given":"William","family":"Cook","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,5]]},"reference":[{"key":"3_CR1","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.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)"},{"key":"3_CR2","first-page":"557","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"David Applegate","year":"1993","unstructured":"Applegate, D.L., Cook, W.: Solving large-scale matching problems. In: Johnson, D.S., McGeoch, C.C. (eds.) Algorithms for Network Flows and Matching. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 12, pp. 557\u2013576. American Mathematical Society, Providence (1993)"},{"key":"3_CR3","unstructured":"Avis, D.: George Dantzig: father of the simplex method. Bull. EATCS 116 (2015)"},{"key":"3_CR4","volume-title":"Dynamic Programming","author":"R Bellman","year":"1957","unstructured":"Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)"},{"key":"3_CR5","doi-asserted-by":"publisher","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. ACM 9, 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"3_CR6","first-page":"1","volume":"101","author":"R Bixby","year":"2016","unstructured":"Bixby, R.: You have to figure out who your customer is going to be. Optima 101, 1\u20136 (2016)","journal-title":"Optima"},{"key":"3_CR7","unstructured":"Bixby, R.: A saga of 25 years of progress in optimization. Lecture at the University of Tokyo, 1 December 2016"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1287\/moor.7.3.441","volume":"7","author":"K-H Borgwardt","year":"1983","unstructured":"Borgwardt, K.-H.: Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex-method. Math. Oper. Res. 7, 441\u2013462 (1983)","journal-title":"Math. Oper. Res."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.22.2.257","volume":"22","author":"R Carr","year":"1997","unstructured":"Carr, R.: Separating clique trees and bipartition inequalities having a fixed number of handles and teeth in polynomial time. Math. Oper. Res. 22, 257\u2013265 (1997)","journal-title":"Math. Oper. Res."},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1287\/moor.2015.0714","volume":"41","author":"K Chandrasekaran","year":"2015","unstructured":"Chandrasekaran, K., V\u00e9gh, L.A., Vempala, S.S.: The cutting plane method is polynomial for perfect matchings. Math. Oper. Res. 41, 23\u201348 (2015)","journal-title":"Math. Oper. Res."},{"key":"3_CR11","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Report no. 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh (1976)"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discret. Math. 4, 305\u2013337 (1973)","journal-title":"Discret. Math."},{"key":"3_CR13","unstructured":"Cobham, A.: The intrinsic computational difficulty of functions. In: Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Sciences, pp. 24\u201330. North Holland, Amsterdam (1965)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/358141.358144","volume":"26","author":"SA Cook","year":"1983","unstructured":"Cook, S.A.: An overview of computational complexity. Commun. ACM 26, 401\u2013408 (1983)","journal-title":"Commun. ACM"},{"key":"3_CR15","unstructured":"Cook, W., Espinoza, D., Goycoolea, M., Helsgaun, K.: US50K (2016). http:\/\/www.math.uwaterloo.ca\/tsp\/us\/index.html"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1287\/ijoc.11.2.138","volume":"11","author":"W Cook","year":"1999","unstructured":"Cook, W., Rohe, A.: Computing minimum-weight perfect matchings. INFORMS J. Comput. 11, 138\u2013148 (1999)","journal-title":"INFORMS J. Comput."},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1287\/mnsc.26.5.495","volume":"26","author":"H Crowder","year":"1980","unstructured":"Crowder, H., Padberg, M.W.: Solving large-scale symmetric travelling salesman problems to optimality. Manag. Sci. 26, 495\u2013509 (1980)","journal-title":"Manag. Sci."},{"key":"3_CR18","first-page":"73","volume":"17","author":"G Dantzig","year":"1948","unstructured":"Dantzig, G.: Programming in a linear structure. Econometrica 17, 73\u201374 (1948)","journal-title":"Econometrica"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large scale traveling salesman problem. Technical report P-510. RAND Corporation, Santa Monica (1954)","DOI":"10.1287\/opre.2.4.393"},{"key":"3_CR20","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393\u2013410 (1954)","journal-title":"Oper. Res."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/MCISE.2000.814652","volume":"2","author":"J Dongara","year":"2000","unstructured":"Dongara, J., Sullivan, F.: The top 10 algorithms. IEEE Comput. Sci. Eng. 2, 22\u201323 (2000)","journal-title":"IEEE Comput. Sci. Eng."},{"key":"3_CR22","unstructured":"Eastman, W.L.: Linear programming with pattern constraints. Ph.D. thesis, Department of Economics, Harvard University, Cambridge (1958)"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stan. 69B, 125\u2013130 (1965)","journal-title":"J. Res. Nat. Bur. Stan."},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"3_CR25","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":"3_CR26","first-page":"32","volume-title":"History of Mathematical Programming-A Collection of Personal Reminiscences","author":"J Edmonds","year":"1991","unstructured":"Edmonds, J.: A glimpse of heaven. In: Lenstra, J.K., et al. (eds.) History of Mathematical Programming-A Collection of Personal Reminiscences, pp. 32\u201354. North-Holland, Amsterdam (1991)"},{"key":"3_CR27","unstructured":"Edmonds, J.: EP and PPA: can it be hard to find if it\u2019s easy to recognize and you know it\u2019s there? Lecture at the 21st Combinatorial Optimization Workshop, Aussois, France, 13 January 2017"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Stan. 71B, 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bur. Stan."},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Stan. 71B, 241\u2013245 (1967)","journal-title":"J. Res. Nat. Bur. Stan."},{"key":"3_CR30","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1287\/moor.24.1.130","volume":"24","author":"L Fleischer","year":"1999","unstructured":"Fleischer, L., Tardos, \u00c9.: Separating maximally violated comb inequalities in planar graphs. Math. Oper. Res. 24, 130\u2013148 (1999)","journal-title":"Math. Oper. Res."},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1287\/opre.4.1.61","volume":"4","author":"MM Flood","year":"1956","unstructured":"Flood, M.M.: The traveling-salesman problem. Oper. Res. 4, 61\u201375 (1956)","journal-title":"Oper. Res."},{"key":"3_CR33","volume-title":"Flows in Networks","author":"LR Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"3_CR34","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01581089","volume":"57","author":"JJ Forrest","year":"1992","unstructured":"Forrest, J.J., Goldfarb, D.: Steepest-edge simplex algorithms for linear programming. Math. Program. 57, 341\u2013274 (1992)","journal-title":"Math. Program."},{"key":"3_CR35","volume-title":"Connections in Combinatorial Optimization","author":"A Frank","year":"2011","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press, Oxford (2011)"},{"key":"3_CR36","unstructured":"Friedmann, O.: Exponential lower bounds for solving infinitary payoff games and linear programs. Ph.D. thesis, Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen (2011)"},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"G\u00f6del, K.: \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme, I. Monats-hefte f\u00fcr Mathematik und Physik 38, 173\u2013198 (1931)","DOI":"10.1007\/BF01700692"},{"key":"3_CR38","first-page":"335","volume":"69","author":"M Goemans","year":"1995","unstructured":"Goemans, M.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335\u2013349 (1995)","journal-title":"Math. Program."},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"3_CR40","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF01593804","volume":"1","author":"D Goldfarb","year":"1977","unstructured":"Goldfarb, D., Reid, J.K.: A practicable steepest-edge simplex algorithm. Math. Program. 1, 361\u2013371 (1977)","journal-title":"Math. Program."},{"key":"3_CR41","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Am. Math. Soc."},{"key":"3_CR42","unstructured":"Gomory, R.E.: The traveling salesman problem. In: Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pp. 93\u2013121. IBM, White Plains (1996)"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0120887","volume":"12","author":"M Gr\u00f6tschel","year":"1980","unstructured":"Gr\u00f6tschel, M.: On the symmetric travelling salesman problem: solution of a 120-city problem. Math. Program. Study 12, 61\u201377 (1980)","journal-title":"Math. Program. Study"},{"key":"3_CR44","unstructured":"Gr\u00f6tschel, M.: Notes for a Berlin Mathematical School (2006)"},{"key":"3_CR45","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel, M., Holland, O.: Solution of large-scale symmetric travelling salesman problems. Math. Program. 51, 141\u2013202 (1991)","journal-title":"Math. Program."},{"key":"3_CR46","doi-asserted-by":"publisher","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","volume":"32","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: A cutting plane algorithm for the linear ordering problem. Oper. Res. 32, 1195\u20131220 (1984)","journal-title":"Oper. Res."},{"key":"3_CR47","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BF01582009","volume":"33","author":"M Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: On the acyclic subgraph polytope. Math. Program. 33, 28\u201342 (1985)","journal-title":"Math. Program."},{"key":"3_CR48","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF01582010","volume":"33","author":"M Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: Facets of the linear ordering polytope. Math. Program. 33, 43\u201360 (1985)","journal-title":"Math. Program."},{"key":"3_CR49","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988). https:\/\/doi.org\/10.1007\/978-3-642-97881-4"},{"key":"3_CR50","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.disopt.2007.08.003","volume":"5","author":"M Gr\u00f6tschel","year":"2008","unstructured":"Gr\u00f6tschel, M., Nemhauser, G.L.: George Dantzig\u2019s contributions to integer programming. Discret. Optim. 5, 168\u2013173 (2008)","journal-title":"Discret. Optim."},{"key":"3_CR51","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285\u2013306 (1965)","journal-title":"Trans. Am. Math. Soc."},{"key":"3_CR52","doi-asserted-by":"publisher","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":"3_CR53","doi-asserted-by":"publisher","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":"3_CR54","first-page":"551","volume":"59","author":"I Heller","year":"1953","unstructured":"Heller, I.: On the problem of the shortest path between points. I. Abstract 664t. Bull. Am. Math. Soc. 59, 551 (1953)","journal-title":"Bull. Am. Math. Soc."},{"key":"3_CR55","first-page":"211","volume":"46","author":"AJ Hoffman","year":"1956","unstructured":"Hoffman, A.J.: Generalization of a theorem of Konig. J. Wash. Acad. Sci. 46, 211\u2013212 (1956)","journal-title":"J. Wash. Acad. Sci."},{"key":"3_CR56","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/0101002","volume":"1","author":"A Hoffman","year":"1953","unstructured":"Hoffman, A., Mannos, M., Sokolowsky, D., Wiegmann, N.: Computational experience in solving linear programs. J. Soc. Ind. Appl. Math. 1, 17\u201333 (1953)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"3_CR57","unstructured":"Hoffman, A.J., Wolfe, P.: History. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem, pp. 1\u201315. Wiley, Chichester (1985)"},{"key":"3_CR58","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR59","unstructured":"Johnson, D.S.: Knuth Prize Lecture (2010)"},{"key":"3_CR60","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Reinelt, G., Thienel, S.: Practical problem solving with cutting plane algorithms. In: Cook, W., Lov\u00e1sz, L., Seymour, P. (eds.) Combinatorial Optimization. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20, pp. 111\u2013152. American Mathematical Society, Providence (1995)","DOI":"10.1090\/dimacs\/020\/02"},{"key":"3_CR61","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF02293053","volume":"8","author":"G Kalai","year":"1992","unstructured":"Kalai, G.: Upper bounds for the diameter and height of graphs of the convex polyhedra. Discret. Comput. Geom. 8, 363\u2013372 (1992)","journal-title":"Discret. Comput. Geom."},{"key":"3_CR62","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"3_CR63","unstructured":"Karp, R.M.: Implicit hitting set problems. Lecture at Harvard University, 29 August 2011"},{"key":"3_CR64","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"BW Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"key":"3_CR65","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671\u2013680 (1983)","journal-title":"Science"},{"key":"3_CR66","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s12532-009-0002-8","volume":"1","author":"V Kolmogorov","year":"2009","unstructured":"Kolmogorov, V.: Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1, 43\u201367 (2009)","journal-title":"Math. Program. Comput."},{"key":"3_CR67","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-3-642-24488-9"},{"key":"3_CR68","first-page":"557","volume":"61","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: On certain convex polyhedra. Abstract 799t. Bull. Am. Math. Soc. 61, 557\u2013558 (1955)","journal-title":"Bull. Am. Math. Soc."},{"key":"3_CR69","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28, 497\u2013520 (1960)","journal-title":"Econometrica"},{"key":"3_CR70","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"3_CR71","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1287\/moor.25.3.443.12213","volume":"25","author":"AN Letchford","year":"2000","unstructured":"Letchford, A.N.: Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. 25, 443\u2013454 (2000)","journal-title":"Math. Oper. Res."},{"key":"3_CR72","doi-asserted-by":"publisher","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S Lin","year":"1965","unstructured":"Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245\u20132269 (1965)","journal-title":"Bell Syst. Tech. J."},{"key":"3_CR73","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498\u2013516 (1973)","journal-title":"Oper. Res."},{"key":"3_CR74","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions, and 0\u20131 optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"3_CR75","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/944618.944622","volume":"7","author":"Kurt Mehlhorn","year":"2002","unstructured":"Mehlhorn, K., Sch\u00e4fer, G.: Implementation of $$O(nm\\log {n})$$ weighted matchings in general graphs: the power of data structures. J. Exp. Algorithmics 7, Article 4 (2002)","journal-title":"Journal of Experimental Algorithmics"},{"key":"3_CR76","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01700678","volume":"38","author":"K Menger","year":"1931","unstructured":"Menger, K.: Bericht \u00fcber ein mathematisches Kolloquium. Monats-hefte f\u00fcr Mathematik und Physik 38, 17\u201338 (1931)","journal-title":"Monats-hefte f\u00fcr Mathematik und Physik"},{"key":"3_CR77","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5, 32\u201338 (1957)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"3_CR78","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1515\/9781400881970-002","volume-title":"Contributions to the Theory of Games (AM-28), Volume II","author":"John von Neumann","year":"1953","unstructured":"von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games, pp. 5\u201312. Princeton University Press, Princeton (1953). (Transcript of a seminar talk given by Professor von Neumann at Princeton University, 26 October 1951)"},{"key":"3_CR79","doi-asserted-by":"crossref","unstructured":"Orden, A.: Solution of systems of linear inequalities on a digital computer. In: Proceedings of the 1952 ACM National Meeting, pp. 91\u201395 (1952)","DOI":"10.1145\/609784.609793"},{"key":"3_CR80","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60\u2013100 (1991)","journal-title":"SIAM Rev."},{"key":"3_CR81","unstructured":"Robinson, J.: Definability and decision problems in arithmetic. Ph.D. thesis, University of California, Berkeley (1948)"},{"key":"3_CR82","unstructured":"Robinson, J.: On the Hamiltonian game (a traveling salesman problem). RAND Research Memorandum RM-303. RAND Corporation, Santa Monica (1949)"},{"key":"3_CR83","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2011","unstructured":"Santos, F.: A counterexample to the Hirsh conjecture. Ann. Math. 176, 383\u2013412 (2011)","journal-title":"Ann. Math."},{"key":"3_CR84","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"key":"3_CR85","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4388-3","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems","author":"HD Sherali","year":"2013","unstructured":"Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-1-4757-4388-3"},{"key":"3_CR86","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51, 385\u2013463 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"3_CR87","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","volume":"s2-42","author":"A. M. Turing","year":"1937","unstructured":"Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. s2-42, 230\u2013265 (1937)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"3_CR88","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"},{"key":"3_CR89","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"3_CR90","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization \u2014 Eureka, You Shrink!","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization \u2014 Eureka, You Shrink!. LNCS, vol. 2570, pp. 185\u2013207. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36478-1_17"}],"container-title":["Lecture Notes in Computer Science","Computing and Software Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-91908-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T14:05:00Z","timestamp":1689084300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-91908-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783319919072","9783319919089"],"references-count":90,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-91908-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}