Better approximations for max TSP

被引：33

作者：

Hassin, R ^{[1
]}

Rubinstein, S

机构：

[1] Tel Aviv Univ, Sch Math Sci, Dept Stat & Operat Res, IL-69978 Tel Aviv, Israel

[2] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA

来源：

INFORMATION PROCESSING LETTERS | 2000年 / 75卷 / 04期

关键词：

analysis of algorithms; maximum traveling salesman; maximum latency TSP;

D O I：

10.1016/S0020-0190(00)00097-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We combine two known polynomial time approximation algorithms for the maximum traveling salesman problem to obtain a randomized algorithm which outputs a solution with expected value of at least r. times the optimal one for any given r < 25/33. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：181 / 186

页数：6