Approximation schemes for the generalized traveling salesman problem

DOI10.1134/S0081543817090127zbMath1390.68764OpenAlexW2793061008MaRDI QIDQ1744982

Katherine Neznakhina, Mikhail Yu. Khachay

Publication date: 20 April 2018

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

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

zbMATH Keywords

NP-hard problempolynomial-time approximation schemegeneralized traveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

Dynamic programming in the routing problem: decomposition variant ⋮ 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 ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters

Uses Software

• GTSP Instances Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a bottleneck routing problem
• The geometric generalized minimum spanning tree problem with grid clustering
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
• Approximation algorithms for the Geometric Covering Salesman Problem
• The Design of Approximation Algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Dynamic Programming Approach to Sequencing Problems
• Approximation Algorithms for Generalized MST and TSP in Grid Clusters
• Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
• The Traveling Salesman Problem for Lines, Balls, and Planes

This page was built for publication: Approximation schemes for the generalized traveling salesman problem