Differential approximation results for the traveling salesman and related problems
Monnot, Jérôme (2002), Differential approximation results for the traveling salesman and related problems, Information Processing Letters, 82, 5, p. 229-235. http://dx.doi.org/10.1016/S0020-0190(01)00287-3
TypeArticle accepté pour publication ou publié
Journal nameInformation Processing Letters
MetadataShow full item record
Abstract (EN)This paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and cannot be differential approximable greater than 649/650. Next, we demonstrate that, when dealing with edge-costs 1 and 2, the same algorithm idea improves this ratio to 3/4 and we obtain a differential non-approximation threshold equal to 741/742. Remark that the 3/4-differential approximation result has been recently proved by a way more specific to the 1-, 2-case and with another algorithm in the recent conference, Symposium on Fundamentals of Computation Theory, 2001. Based upon these results, we establish new bounds for standard ratio: 5/6 for Max TSP[a,2a] and 7/8 for Max TSP[1,2]. We also derive some approximation results on partition graph problems by paths.
Subjects / KeywordsAnalysis of algorithms; Performance ratio; Differential ratio; Approximation algorithms
Showing items related by title and author.