35/44‐approximation for Asymmetric Maximum TSP with Triangle Inequality

35/44‐approximation for Asymmetric Maximum TSP with Triangle Inequality

0.00 Avg rating0 Votes
Article ID: iaor20112030
Volume: 59
Issue: 2
Start Page Number: 240
End Page Number: 255
Publication Date: Feb 2011
Journal: Algorithmica
Authors: ,
Keywords: approximation algorithms
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.