Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
DOI10.1007/S10472-019-09626-WzbMATH Open1430.90491OpenAlexW2932662651WikidataQ128203861 ScholiaQ128203861MaRDI QIDQ2294592FDOQ2294592
Katherine Neznakhina, M. Yu. Khachaĭ
Publication date: 11 February 2020
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-019-09626-w
Recommendations
- Approximation schemes for the generalized traveling salesman problem
- Approximation algorithms for generalized MST and TSP in grid clusters
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- On the complexity of approximating TSP with neighborhoods and related problems
- On the complexity of approximating TSP with neighborhoods and related problems
polynomial-time approximation schemegeneralized traveling salesman problempolynomial-time solvable subclass
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The Euclidean traveling salesman problem is NP-complete
- Bounds and Heuristics for Capacitated Routing Problems
- Approximation algorithms for TSP with neighborhoods in the plane
- Title not available (Why is that?)
- A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- The traveling salesman problem and its variations.
- Approximability of the minimum-weight \(k\)-size cycle cover problem
- Approximation algorithms for the Geometric Covering Salesman Problem
- New classes of efficiently solvable generalized traveling salesman problems
- The geometric generalized minimum spanning tree problem with grid clustering
- Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
- Approximation schemes for the generalized traveling salesman problem
- Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
- APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
- Generalized pyramidal tours for the generalized traveling salesman problem
- The Traveling Salesman Problem for Lines, Balls, and Planes
- Approximation Algorithms for Generalized MST and TSP in Grid Clusters
- An exact algorithm with linear complexity for a problem of visiting megalopolises
Cited In (7)
- 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
- Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
- Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem
- Parameter tuning of continuous Hopfield network applied to combinatorial optimization
- Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
- A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane
Uses Software
This page was built for publication: Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294592)
