An approximation algorithm for a bottleneck traveling salesman problem

DOI10.1016/j.jda.2008.11.007zbMath1190.68082OpenAlexW2057741299MaRDI QIDQ1026245

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

job sequencingtwo-machine flowshopbottleneck traveling salesman problemnuclear magnetic resonance spectroscopyreconstruction from inaccurate adjacency

Mathematics Subject Classification ID

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

Related Items (3)

Solution algorithms for synchronous flow shop problems with two dominating machines ⋮ Complexity analysis of balloon drawing for rooted trees ⋮ Experimental analysis of heuristics for the bottleneck traveling salesman problem

Cites Work

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

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