Better approximations for max TSP

Authors
Hassin, R Rubinstein, S
Citation
R. Hassin et S. Rubinstein, Better approximations for max TSP, INF PROCESS, 75(4), 2000, pp. 181-186
Citations number
5
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
75
Issue
4
Year of publication
2000
Pages
181 - 186
Database
ISI
SICI code
0020-0190(20000930)75:4<181:BAFMT>2.0.ZU;2-X
Abstract
We combine two known polynomial time approximation algorithms for the maxim um traveling salesman problem to obtain a randomized algorithm which output s a solution with expected value of at least r. times the optimal one for a ny given r < 25/33. (C) 2000 Elsevier Science B.V. All rights reserved.