Improved deterministic approximation algorithms for Max TSP

被引：20

作者：

Chen, ZZ ^{[1
]}

Okamoto, Y

Wang, LS

机构：

[1] Tokyo Denki Univ, Dept Math Sci, Hatosyama, Saitama 3500394, Japan

[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

[3] City Univ Hong Kong, Hong Kong, Hong Kong, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2005年 / 95卷 / 02期

关键词：

approximation algorithms; graph algorithms; randomized algorithms;

D O I：

10.1016/j.ipl.2005.03.011

中图分类号：

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

学科分类号：

0812 ;

摘要：

We present an O(n(3))-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 61/81, where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n(3))-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically 17/20. Both algorithms improve on the previous bests. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：333 / 342

页数：10

共 10 条

[1]

Barvinok A, 1998, LECT NOTES COMPUT SC, V1412, P195

[2]

CHEN ZG, UNPUB

[3]

Chen ZZ, 1996, THEOR COMPUT SCI, V161, P1, DOI 10.1016/0304-3975(95)00110-7

[4] An approximation algorithm for the maximum traveling salesman problem [J].

Hassin, R ;

Rubinstein, S .

INFORMATION PROCESSING LETTERS, 1998, 67 (03) :125-130

[5] Better approximations for max TSP [J].

Hassin, R ;

Rubinstein, S .

INFORMATION PROCESSING LETTERS, 2000, 75 (04) :181-186

[6] A 7/8-approximation algorithm for metric max TSP [J].

Hassin, R ;

Rubinstein, S .

INFORMATION PROCESSING LETTERS, 2002, 81 (05) :247-251

[7] CONSTRUCTING A PERFECT MATCHING IS IN RANDOM NC [J].

KARP, RM ;

UPFAL, E ;

WIGDERSON, A .

COMBINATORICA, 1986, 6 (01) :35-48

[8]

KOSTOCHKA AV, 1985, UPRAVLYAEMYE SISTEMY, V26, P55

[9] MATCHING IS AS EASY AS MATRIX-INVERSION [J].

MULMULEY, K ;

VAZIRANI, UV ;

VAZIRANI, VV .

COMBINATORICA, 1987, 7 (01) :105-113

[10]

SERDYUKOV AI, 1984, UPRAVLYAEMYE SISTEMY, V25, P80

← 1 →