A 7/8-approximation algorithm for metric max TSP

被引：27

作者：

Hassin, R ^{[1
]}

Rubinstein, S ^{[1
]}

机构：

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

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 81卷 / 05期

关键词：

analysis of algorithms; maximum traveling salesman problem;

D O I：

10.1016/S0020-0190(01)00234-4

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present a randomized approximation algorithm for the metric version of undirected Max TSP. Its expected performance 7/8 as n --> infinity, where n is the number of vertices in the graph. (C) 2002 Elsevier Science B.V. All rights guarantee reserved.

引用

页码：247 / 251

页数：5