35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality

DOI10.1007/978-3-540-73951-7_51MaRDI QIDQ3603560zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Marcin Mucha

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_51

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• 35/44-approximation for asymmetric maximum TSP with triangle inequality
• Simpler approximation of the maximum asymmetric traveling salesman problem
• scientific article; zbMATH DE number 2038707
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• An improved approximation algorithm for the ATSP with parameterized triangle inequality

Cited in

(16)

• scientific article; zbMATH DE number 2079395 (Why is no real title available?)
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Deterministic 7/8-approximation for the metric maximum TSP
• Simpler approximation of the maximum asymmetric traveling salesman problem
• Deterministic 7/8-Approximation for the Metric Maximum TSP
• 35/44-approximation for asymmetric maximum TSP with triangle inequality
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• A note on the approximation of the asymmetric traveling salesman problem.
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• A new approximation algorithm for the asymmetric TSP with triangle inequality
• Analysis of set-up time models: a metric perspective
• Approximation algorithms for maximum latency and partial cycle cover
• STACS 2004
• scientific article; zbMATH DE number 2079394 (Why is no real title available?)
• A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP

This page was built for publication: 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality

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