A Dynamic Programming Approach to Sequencing Problems

Abstract

Previous article Next article A Dynamic Programming Approach to Sequencing ProblemsMichael Held and Richard M. KarpMichael Held and Richard M. Karphttps://doi.org/10.1137/0110015PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] R. L. Ackoff, Progress in Operations Research, Vol. I, Publications in Operations Research, No. 5, John Wiley & Sons Inc., New York, 1961xii+505 MR0121239 Google Scholar[2A] Richard Bellman, Combinatorial processes and dynamic programmingProc. Sympos. Appl. Math., Vol. 10, American Mathematical Society, Providence, R.I., 1960, 217–249 MR0113718 0096.14506 CrossrefGoogle Scholar[2B] Richard Bellman, Dynamic programming treatment of the travelling salesman problem, J. Assoc. Comput. Mach., 9 (1962), 61–63 MR0135702 0106.14102 CrossrefISIGoogle Scholar[3] G. A. Croes, A method for solving traveling-salesman problems, Operations Res., 6 (1958), 791–812 MR0099887 CrossrefISIGoogle Scholar[4A] G. Dantzig, , R. Fulkerson and , S. Johnson, Solution of a large-scale traveling-salesman problem, J. Operations Res. Soc. Amer., 2 (1954), 393–410 MR0070932 CrossrefISIGoogle Scholar[4B] G. B. Dantzig, , D. R. Fulkerson and , S. M. Johnson, On a linear-programming, combinatorial approach to the traveling-salesman problem, Operations Res., 7 (1959), 58–66 MR0101823 CrossrefISIGoogle Scholar[5] Kurt Eisemann, The trim problem, Management Sci., 3 (1957), 279–284 MR0088407 0995.92500 CrossrefISIGoogle Scholar[6] Merrill M. Flood, The traveling-salesman problem, Operations Res., 4 (1956), 61–75 MR0078639 CrossrefISIGoogle Scholar[7] P. C. Gilmore and , R. E. Gomory, A linear programming approach to the cutting-stock problem, Operations Res., 9 (1961), 849–859 MR0137589 0096.35501 CrossrefISIGoogle Scholar[8] Maurice Kraitchik, Mathematical recreations, Dover Publications Inc., New York, N. Y., 1953, 330–, Chapter 11 MR0052446 0050.00901 Google Scholar[9] Robert McNaughton, Scheduling with deadlines and loss functions, Management Sci., 6 (1959/1960), 1–12 MR0110585 1047.90504 CrossrefISIGoogle Scholar[10] M. E. Salveson, The assembly line balancing problem, Journal of Industrial Engineering, 6 (1955), 18–25 Google Scholar[11] B. L. van der Waerden, Modern Algebra. Vol. I, Frederick Ungar Publishing Co., New York, N. Y., 1949xii+264 MR0029363 Google Scholar Previous article Next article FiguresRelatedReferencesCited byDetails Approximation Limitations of Pure Dynamic ProgrammingStasys Jukna and Hannes Seiwert18 February 2020 | SIAM Journal on Computing, Vol. 49, No. 1AbstractPDF (676 KB)On the Fine-Grained Complexity of Rainbow ColoringŁukasz Kowalik, Juho Lauri, and Arkadiusz Socała17 July 2018 | SIAM Journal on Discrete Mathematics, Vol. 32, No. 3AbstractPDF (640 KB)Bounding the Running Time of Algorithms for Scheduling and Packing ProblemsK. Jansen, F. Land, and K. Land25 February 2016 | SIAM Journal on Discrete Mathematics, Vol. 30, No. 1AbstractPDF (382 KB)Tropical Complexity, Sidon Sets, and Dynamic ProgrammingStasys Jukna1 November 2016 | SIAM Journal on Discrete Mathematics, Vol. 30, No. 4AbstractPDF (507 KB)Determinant Sums for Undirected HamiltonicityAndreas Björklund20 February 2014 | SIAM Journal on Computing, Vol. 43, No. 1AbstractPDF (314 KB)Symmetry Matters for Sizes of Extended FormulationsVolker Kaibel, Kanstantsin Pashkovich, and Dirk Oliver Theis18 September 2012 | SIAM Journal on Discrete Mathematics, Vol. 26, No. 3AbstractPDF (329 KB)Parameterized Complexity of Arc-Weighted Directed Steiner ProblemsJiong Guo, Rolf Niedermeier, and Ondřej Suchý27 June 2011 | SIAM Journal on Discrete Mathematics, Vol. 25, No. 2AbstractPDF (268 KB)Set Partitioning via Inclusion-ExclusionAndreas Björklund, Thore Husfeldt, and Mikko Koivisto23 July 2009 | SIAM Journal on Computing, Vol. 39, No. 2AbstractPDF (265 KB)Exact Algorithms for Treewidth and Minimum Fill-InFedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger2 July 2008 | SIAM Journal on Computing, Vol. 38, No. 3AbstractPDF (265 KB)The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman ProblemsAlan Frieze and Gregory B. Sorkin26 January 2007 | SIAM Journal on Computing, Vol. 36, No. 5AbstractPDF (235 KB)Expected Computation Time for Hamiltonian Path problemYuri Gurevich and Saharon Shelah13 July 2006 | SIAM Journal on Computing, Vol. 16, No. 3AbstractPDF (2164 KB)The Traveling Salesman Problem with Many Visits to Few CitiesStavros S. Cosmadakis and Christos H. Papadimitriou2 August 2006 | SIAM Journal on Computing, Vol. 13, No. 1AbstractPDF (1209 KB)The Travelling Salesman Problem and Minimum Matching in the Unit SquareKenneth J. Supowit, Edward M. Reingold, and David A. Plaisted31 July 2006 | SIAM Journal on Computing, Vol. 12, No. 1AbstractPDF (1169 KB)A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability OneJ. H. Halton and R. Terada31 July 2006 | SIAM Journal on Computing, Vol. 11, No. 1AbstractPDF (1669 KB)Algorithms for Obtaining Shortest Paths Visiting Specified NodesToshihide Ibaraki2 August 2006 | SIAM Review, Vol. 15, No. 2AbstractPDF (772 KB)Finite-State Processes and Dynamic ProgrammingRichard M. Karp and Michael Held13 July 2006 | SIAM Journal on Applied Mathematics, Vol. 15, No. 3AbstractPDF (2840 KB)Discrete OptimizingStanley Reiter and Gordon Sherman13 July 2006 | Journal of the Society for Industrial and Applied Mathematics, Vol. 13, No. 3AbstractPDF (2288 KB) Volume 10, Issue 1| 1962Journal of the Society for Industrial and Applied Mathematics History Submitted:31 August 1961Published online:13 July 2006 InformationCopyright © 1962 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0110015Article page range:pp. 196-210ISSN (print):0368-4245ISSN (online):2168-3484Publisher:Society for Industrial and Applied Mathematics