Dynamic Programming Treatment of the Travelling Salesman Problem
From MaRDI portal
Publication:3292043
DOI10.1145/321105.321111zbMath0106.14102OpenAlexW1971483538WikidataQ55899755 ScholiaQ55899755MaRDI QIDQ3292043
Publication date: 1962
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321105.321111
Related Items
On sequential traversal of sets, An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization, Richard Bellman's contributions to computer science, On Cutwidth Parameterized by Vertex Cover, Embedded local search approaches for routing optimization, Hybrid functions of Bernstein polynomials and block-pulse functions for solving optimal control of the nonlinear Volterra integral equations, On residual approximation in solution extension problems, Algebraic dynamic programming for multiple context-free grammars, A 3/2-Approximation for the Metric Many-Visits Path TSP, Particle swarm optimization-based algorithms for TSP and generalized TSP, The bi-objective mixed capacitated general routing problem with different route balance criteria, On solving manufacturing cell formation via bicluster editing, Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs, One task of routing jobs in high radiation conditions, A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem, Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths, The dynamic programming method in the generalized traveling salesman problem, Solving the job-shop scheduling problem optimally by dynamic programming, Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times, An exact algorithm with linear complexity for a problem of visiting megalopolises, Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension, Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem, Solving large-scale TSP using a fast wedging insertion partitioning approach, Deep policy dynamic programming for vehicle routing problems, Parameterized complexity of superstring problems, On global integer extrema of real-valued box-constrained multivariate quadratic functions, End-Vertices of Graph Search Algorithms, On the complexity landscape of connected \(f\)-factor problems, Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries, Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals, The traveling purchaser problem with stochastic prices: exact and approximate algorithms, Evaluation of permanents in rings and semirings, A new graph model and algorithms for consistent superstring problems , Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach, Dynamic graph conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem, Optimizing multi-inserts in routing problems with constraints, On the question of the optimization of permutations in the problem with dynamic constraints, About an optimal visiting problem, An exact algorithm for the Boolean connectivity problem for \(k\)-CNF, Finding a Hamilton cycle fast on average using rotations and extensions, Probabilistic analysis of solving the assignment problem for the traveling salesman problem, Parameterised temporal exploration problems, OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS, An extremal constrained routing problem with internal losses, On the relationship between the biconnectivity augmentation and traveling salesman problems, An alternate formulation of the symmetric traveling salesman problem and its properties, A genetic algorithm for a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times, Fast monotone summation over disjoint sets, Problem of successive megalopolis traversal with the precedence conditions, Solving SCS for bounded length strings in fewer than \(2^n\) steps, Problem of optimal choice of a route under conditions of time discounting, On cutwidth parameterized by vertex cover, Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis, Randomized sampling for large zero-sum games, Finding supported paths in heterogeneous networks, Special Frequency Quadrilaterals and an Application, A geometrical method in combinatorial complexity, Dynamic programming with convexity, concavity and sparsity, Reaching a joint decision with minimal elicitation of voter preferences, Clustering with Local Restrictions, Invitation to Algorithmic Uses of Inclusion–Exclusion, Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials, Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization, Temporal ordering of substitutions in RNA evolution: uncovering the structural evolution of the Human Accelerated Region 1, Unnamed Item, A new upper bound for the traveling salesman problem in cubic graphs, Design tools for reporter strands and DNA origami scaffold strands, Reduced complexity dynamic programming based on policy iteration, Restricted dynamic programming: a flexible framework for solving realistic VRPs, Vehicle routing under time-dependent travel times: the impact of congestion avoidance, Constrained optimal routing, Dynamic programming in the routing problem with complex dependence of costs on the list of jobs, Finding paths of length \(k\) in \(O^{*}(2^k)\) time, On pedigree polytopes and Hamiltonian cycles, Unnamed Item, Unnamed Item, Some optimal path problems subject to improvements, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Solving a Routing Problem with the Aid of an Independent Computations Scheme, The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem, On one routing problem modeling movement in radiation fields, Domino sequencing: scheduling with state-based sequence-dependent setup times, Оptimization of the Start Point in the Gtsp with the Precedence Conditions, Many-visits TSP revisited, A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, Algorithms in unnormalized arithmetic. III: Matrix inversion, The Königsberg bridges problem generalized, Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks, Hybrid control for optimal visiting problems for a single player and for a crowd, ON ROUTING PROBLEM WITH STARTING POINT OPTIMIZATION, On the problem of sequential traversal of megalopolises with precedence conditions and cost functions depending on a list of tasks, Computing in combinatorial optimization, Parameterized algorithms and complexity for the traveling purchaser problem and its variants, The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem, The traveling salesman problem with few inner points, Faster exponential-time algorithms in graphs of bounded average degree, Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version, A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals, A memetic algorithm for the multiperiod vehicle routing problem with profit, Review of sequencing research, Some constrained shortest-route problems, A general framework for enumerating equivalence classes of solutions, Combining incomplete search and clause generation: an application to the orienteering problems with time windows, Multidistances and inequality measures on abstract sets: an axiomatic approach, Two-stage dynamic programming in the routing problem with decomposition, Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems, Exact and anytime approach for solving the time dependent traveling salesman problem with time windows, Energy minimizing order picker forklift routing problem, A 3/4 differential approximation algorithm for traveling salesman problem, Minimax routing problem with a system of priority tasks, Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals, On the Application of the Minimax Traveling Salesman Problem in Aviation Logistics, An ETH-Tight Exact Algorithm for Euclidean TSP, A bi-criteria moving-target travelling salesman problem under uncertainty, A bottleneck routing problem with a system of priority tasks, A note on a single-shift days-off scheduling problem with sequence-dependent labor costs, The single robot line coverage problem: Theory, algorithms, and experiments, Time complexity of the analyst's traveling salesman algorithm, Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows, Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems, On one routing task with the optimization of the start-finish point, The routing problems with optimization of the starting point: dynamic programming, Collapsing Superstring Conjecture, To the question of optimization of the starting point in the routing problem with restrictions, The Asymmetric Travelling Salesman Problem In Sparse Digraphs., Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, Dynamic programming method in the generalized traveling salesman problem: the influence of inexact calculations., On the complexity of discrete programming problems, Unnamed Item, Dynamic programming based metaheuristics for the dial-a-ride problem, Disjoint paths and connected subgraphs for \(H\)-free graphs, Disjoint paths and connected subgraphs for \(H\)-free graphs, Fast exact algorithms for survivable network design with uniform requirements, Unnamed Item, Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding
