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

DOI10.1007/978-3-540-73951-7_51zbMATH Open1209.68646OpenAlexW1829077348MaRDI QIDQ3603560FDOQ3603560

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

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

Mathematics Subject Classification ID

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

Cited In (17)

• 35/44-approximation for asymmetric maximum TSP with triangle inequality
• Deterministic 7/8-approximation for the metric maximum TSP
• Title not available (Why is that?)
• A note on the approximation of the asymmetric traveling salesman problem.
• Maximum ATSP with weights zero and one via half-edges
• STACS 2004
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• Approximation algorithms for maximum latency and partial cycle cover
• Title not available (Why is that?)
• Simpler approximation of the maximum asymmetric traveling salesman problem
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• A new approximation algorithm for the asymmetric TSP with triangle inequality
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
• Deterministic 7/8-Approximation for the Metric Maximum TSP
• A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP
• Analysis of set-up time models: a metric perspective

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)