An improved randomized approximation algorithm for max TSP

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

9 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)401-432
Journal / PublicationJournal of Combinatorial Optimization
Issue number4
Publication statusPublished - Jun 2005


We present an O(n 3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically 251/331, where n is the number of vertices in the input (undirected) graph. This improves the previous best. © 2005 Springer Science + Business Media, Inc.

Research Area(s)

  • Approximation algorithms, Graph algorithms, Max TSP, Randomized algorithms