Approximation schemes for the generalized traveling salesman problem

DOI10.1134/S0081543817090127zbMATH Open1390.68764OpenAlexW2793061008MaRDI QIDQ1744982FDOQ1744982

Authors: M. Yu. Khachaĭ, Katherine Neznakhina 

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

Recommendations

• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• scientific article; zbMATH DE number 1302021
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Approximation algorithms for generalized MST and TSP in grid clusters

zbMATH Keywords

polynomial-time approximation schemeNP-hard problemgeneralized 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)

Cites Work

• The design of approximation algorithms
• A Dynamic Programming Approach to Sequencing Problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Approximation algorithms for TSP with neighborhoods in the plane
• A PTAS for TSP with neighborhoods among fat regions in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• The geometric generalized minimum spanning tree problem with grid clustering
• On a bottleneck routing problem
• Title not available (Why is that?)
• Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
• Title not available (Why is that?)
• Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
• The traveling salesman problem for lines, balls, and planes
• Approximation algorithms for generalized MST and TSP in grid clusters

Cited In (18)

• Metaheuristics for the distance constrained generalized covering traveling salesman problem
• Generalized traveling salesman problem reduction algorithms
• Approximation algorithms for generalized MST and TSP in grid clusters
• Fault-tolerant families of production plans: mathematical model, computational complexity, and branch-and-bound algorithms
• Reliable production process design problem: compact MILP model and ALNS-based primal heuristic
• Approximation algorithms for multi-criteria traveling salesman problems
• Title not available (Why is that?)
• Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
• Title not available (Why is that?)
• Multi-candidate carpooling routing problem and its approximation algorithms
• Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• The reduction of the Pareto set of a special structure in bicriteria discrete problems
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• Dynamic programming in the routing problem: decomposition variant
• Title not available (Why is that?)
• GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem
• A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane

Uses Software

• GTSP Instances Library

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1744982)