The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis

DOI10.1016/J.COR.2013.08.005zbMATH Open1348.90546OpenAlexW2106727356MaRDI QIDQ336878FDOQ336878

Authors: John LaRusic, Abraham P. Punnen 

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2013.08.005

Recommendations

• Approximation algorithms for the bottleneck asymmetric traveling salesman problem
• Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
• A note on the complexity of the asymmetric traveling salesman problem
• A study of complexity transitions on the asymmetric traveling salesman problem
• A comparative analysis of several asymmetric traveling salesman problem formulations
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• scientific article; zbMATH DE number 1893558
• A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem

zbMATH Keywords

heuristicscomplexityapproximation algorithmstraveling salesman problemexperimental analysisbottleneck problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Network flows. Theory, algorithms, and applications.
• The traveling salesman problem and its variations
• Bottleneck extrema
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• The Bottleneck Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• An efficient heuristic algorithm for the bottleneck traveling salesman problem
• Experimental analysis of heuristics for the bottleneck traveling salesman problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Title not available (Why is that?)
• Minmax combinatorial optimization
• A short proof of Meyniel's theorem
• Algorithms for the minimax problem of the traveling salesman. I: An approach based on dynamic programming
• A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem
• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• An upper bound for the Hamiltonicity exponent of finite digraphs
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• A fast algorithm for a class of bottleneck problems
• On Hamiltonian powers of digraphs
• Title not available (Why is that?)
• An Algorithm for the Bottleneck Traveling Salesman Problem
• Title not available (Why is that?)
• Minimax 2-connected subgraphs and the bottleneck traveling salesman problem
• Title not available (Why is that?)
• A data-guided lexisearch algorithm for the asymmetric traveling salesman problem
• On the Maximum Scatter Traveling Salesperson Problem
• Title not available (Why is that?)
• Transforming asymmetric into symmetric traveling salesman problems
• Minmax strongly connected subgraphs with node penalties

Cited In (22)

• Some remarks on two degrees of asymmetry in the traveling salesman problem
• The research of optimal down bound of asymmetrical TSP
• An Algorithm for the Bottleneck Traveling Salesman Problem
• Title not available (Why is that?)
• Minimizing the number of workers in a paced mixed-model assembly line
• A data-guided lexisearch algorithm for the bottleneck travelling salesman problem
• High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system
• Experimental analysis of heuristics for the bottleneck traveling salesman problem
• The balanced traveling salesman problem
• Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin-Marsten bounding
• Title not available (Why is that?)
• The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• An Approximation Algorithm for a Bottleneck Traveling Salesman Problem
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• An approximation algorithm for a bottleneck traveling salesman problem
• Approximation algorithms for the bottleneck asymmetric traveling salesman problem
• A class of exponential neighbourhoods for the quadratic travelling salesman problem
• A branch-and-cut algorithm for the balanced traveling salesman problem
• Perturbation analysis of practical algorithms for the maximum scatter travelling salesman problem
• A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions
• Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem

Uses Software

• TSPLIB
• LKH
• Concorde

This page was built for publication: The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis

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