SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS

DOI10.1080/10637199708915622zbMATH Open0873.68091OpenAlexW2048039662MaRDI QIDQ3130161FDOQ3130161

Authors: Keqin Li 

Publication date: 9 October 1997

Published in: Parallel Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10637199708915622

Recommendations

• The parallel complexity of TSP heuristics
• The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP
• New parallel randomized algorithms for the traveling salesman problem
• scientific article; zbMATH DE number 808804
• scientific article; zbMATH DE number 4093206

zbMATH Keywords

traveling salesmanMonte Carlo CREW PRAM algorithm

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Cites Work

• Title not available (Why is that?)
• An Algorithm for the Traveling Salesman Problem
• Title not available (Why is that?)
• A Dynamic Programming Approach to Sequencing Problems
• Title not available (Why is that?)
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Hamilton Paths in Grid Graphs
• Title not available (Why is that?)
• P-Complete Approximation Problems
• Title not available (Why is that?)
• An Efficient Parallel Biconnectivity Algorithm
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• On the Complexity of Local Search for the Traveling Salesman Problem
• Parallel algorithms for the connected components and minimal spanning tree problems
• Efficient parallel algorithms for some graph problems
• Tight bounds for christofides' traveling salesman heuristic
• Finding Euler tours in parallel

Cited In (4)

• Title not available (Why is that?)
• On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
• Title not available (Why is that?)
• New parallel randomized algorithms for the traveling salesman problem

This page was built for publication: SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS

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