An exact algorithm with linear complexity for a problem of visiting megalopolises

DOI10.1134/S0081543816090054zbMath1375.90247OpenAlexW2582089955MaRDI QIDQ2396369

Yanyan Li

Publication date: 8 June 2017

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0081543816090054

zbMATH Keywords

dynamic programmingtraveling salesman problemNP-hard problemprecedence relations

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

The reduction of the Pareto set of a special structure in bicriteria discrete problems, Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm, A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane, Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem, OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS, Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic programming in the routing problem with constraints and costs depending on a list of tasks
• Problem of successive megalopolis traversal with the precedence conditions
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Approximability of the problem about a minimum-weight cycle cover of a graph
• The traveling salesman problem. II: Exact methods
• On the complexity of dynamic programming for sequencing problems with precedence constraints
• New classes of efficiently solvable generalized traveling salesman problems
• Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
• To question of routing of works complexes
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Reducibility among Combinatorial Problems