An approximation algorithm for a bottleneck traveling salesman problem

DOI10.1016/J.JDA.2008.11.007MaRDI QIDQ1026245zbMATH OpenOpenAlexFDO

Authors Ming-Yang Kao, Manan Sanghi

Publication date 24 June 2009

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.11.007

zbMATH Keywords

bottleneck traveling salesman problemjob sequencingtwo-machine flowshopnuclear magnetic resonance spectroscopyreconstruction from inaccurate adjacency

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• An Approximation Algorithm for a Bottleneck Traveling Salesman Problem
• An efficient heuristic algorithm for the bottleneck traveling salesman problem
• On Gilmore-Gomory's open question for the bottleneck TSP.
• An Algorithm for the Bottleneck Traveling Salesman Problem
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis

Cites work

• scientific article; zbMATH DE number 5764790 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 8/7-approximation algorithm for (1,2)-TSP
• Approximation algorithms for NMR spectral peak assignment.
• Four point conditions and exponential neighborhoods for symmetric TSP
• Model-Based Assignment and Inference of Protein Backbone Nuclear Magnetic Resonances
• On Gilmore-Gomory's open question for the bottleneck TSP.
• On the Flow-Shop Sequencing Problem with No Wait in Process^†
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Simple algorithms for gilmore-gomory's traveling salesman and related problems
• The traveling salesman problem and its variations
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

Cited in

(10)

• scientific article; zbMATH DE number 598850 (Why is no real title available?)
• scientific article; zbMATH DE number 1688388 (Why is no real title available?)
• Experimental analysis of heuristics for the bottleneck traveling salesman problem
• THE TRAVELING SALESMAN PROBLEM: APPROXIMATE ALGORITHM BY BRANCH-AND-BOUND METHOD WITH GUARANTEED PRECISION
• Complexity analysis of balloon drawing for rooted trees
• Solution algorithms for synchronous flow shop problems with two dominating machines
• An Approximation Algorithm for a Bottleneck Traveling Salesman Problem
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• An efficient heuristic algorithm for the bottleneck traveling salesman problem
• On Gilmore-Gomory's open question for the bottleneck TSP.

This page was built for publication: An approximation algorithm for a bottleneck traveling salesman problem

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