A dynamic programming approach to sequencing problems

By M. Held, Richard M. Karp. 1962

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Towards Better Analysis of Deep Convolutional Neural Networks (2016, methodology): “This combinational optimization problem can be solved by the HeldKarp algorithm [23] with a time complexity of O(2NC ·N2 C), where NC is the number of neurons.”
Exact Algorithms for NP-Hard Problems: A Survey (2001, methodology): “We now sketch the exact TSP algorithm of Held & Karp [16] that is based on dynamic programming across the subsets.”
Set Partitioning via Inclusion-Exclusion (2009, methodology): “However, we can enumerate all vertex subsets U such that G[U ] is Hamiltonian in time O∗(2n) [26].”
The traveling salesman problem and its variations (2007, methodology): “The well-known Held-Karp dynamic programming algorithm [ 28 ] solves the ATSP to optimality in time O(n22n).”
Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on State-space-time Network Representations (2015, methodology): “To define passengers’ service patterns, we utilize the path representation for the Traveling Salesman Problem (TSP) suggested by Bellman (1962) and Held and Karp (1962).”
Lower bounds based on the Exponential Time Hypothesis (2011, unknown): “A variant of ETH, called the Strong Exponential Time Hypothesis (SETH) can be used to give even more refined lower bounds saying, e.g., that a parameterized problem cannot be solved in time (2 ")knO(1) for any " > 1.”
Dynamic vehicle routing problems: Three decades and counting (2016, background): “Perhaps as an extreme example, the memory requirement to solve the Traveling Salesman Problem (TSP) exactly by dynamic programming grows as O (n2 n ), where n is the number of nodes, and CPU time grows as O (n 2 2 n ) (Held and Karp, 1962).”
Vehicle routing under time-dependent travel times: The impact of congestion avoidance (2012, methodology): “The restricted DP heuristic for the VRP is based on the exact DP algorithm for the TSP of Held and Karp [24] and Bellman [25].”
The NP-Completeness Column: An Ongoing Guide (1982, methodology): “For example, whenever the algorithm fails to find a circuit, we could call as a subroutine the O(n 22n ) dynamic programming algorithm of [23], which is”
Dynamic programming approaches for the traveling salesman problem with drone (2017, unknown): “In this section we present dynamic programming approaches for the TSP-D based on the well-known Bellman-Held-Karp dynamic programming algorithm for the TSP [3, 10].”
An Effective Heuristic Algorithm for the Traveling-Salesman Problem (1973, background): “For instance, in the 48-city problem[4] on over 200 trials, we obtain only four distinct solutions (11461, 11474, 11508, 11574) with relative frequencies 0.”
Getting Things in Order: An Introduction to the R Package seriation (2008, background): “However, despite this vast searching space, small instances can be solved eﬃciently using dynamic programming (Held and Karp 1962) and larger instances of several hundred objects can be solved using branch-and-cut algorithms (Padberg and Rinaldi 1990).”