Article ID: | iaor20112030 |
Volume: | 59 |
Issue: | 2 |
Start Page Number: | 240 |
End Page Number: | 255 |
Publication Date: | Feb 2011 |
Journal: | Algorithmica |
Authors: | Kowalik Lukasz, Mucha Marcin |
Keywords: | approximation algorithms |
We describe a new approximation algorithm for the asymmetric maximum traveling salesman problem (ATSP) with triangle inequality. Our algorithm achieves approximation factor 35/44 which improves on the previous 31/40 factor of Bläser, Ram and Sviridenko (2005).