Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem

DOI10.1145/3478537MaRDI QIDQ5035879zbMATH OpenOpenAlexFDO

Authors Hyung-Chan An, David B. Shmoys, Robert D. Kleinberg

Publication date 22 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.14233

zbMATH Keywords

approximation algorithmsbottleneck optimizationtraveling salesman problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for the bottleneck asymmetric traveling salesman problem
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• The asymmetric traveling salesman problem on graphs with bounded genus

Cited in

(7)

• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 5899262 (Why is no real title available?)
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• PTAS for Euclidean travelling salesman problem with soft time windows
• Noncrossing longest paths and cycles
• Noncrossing longest paths and cycles
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme

This page was built for publication: Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem

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