An approximation algorithm for the maximum traveling salesman problem

被引：16

作者：

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 | 1998年 / 67卷 / 03期

关键词：

analysis of algorithms; maximum traveling salesman;

D O I：

10.1016/S0020-0190(98)00102-1

中图分类号：

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

学科分类号：

0812 ;

摘要：

We develop a polynomial time approximation algorithm for the maximum traveling salesman problem. It guarantees a solution value of at least r times the optimal one for any given r < 5/7. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：125 / 130

页数：6

共 10 条

[1] A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM
ALON, N
BABAI, L
ITAI, A
[J]. JOURNAL OF ALGORITHMS, 1986, 7 (04) : 567 - 583
[2] Two algorithmic results for the traveling salesman problem
Barvinok, AI
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1996, 21 (01) : 65 - 84
[3] BARVINOK AI, 1998, FINDING MAXIMUM LENG
[4] BHATIA R, COMMUNICATION
[5] MAXIMIZING TRAVELING SALESMAN PROBLEM FOR SPECIAL MATRICES
BLOKH, D
GUTIN, G
[J]. DISCRETE APPLIED MATHEMATICS, 1995, 56 (01) : 83 - 86
[6] DEINEKO VG, MAXIMUM TRAVELING SA
[7] ANALYSIS OF APPROXIMATIONS FOR FINDING A MAXIMUM WEIGHT HAMILTONIAN CIRCUIT
FISHER, ML
NEMHAUSER, GL
WOLSEY, LA
[J]. OPERATIONS RESEARCH, 1979, 27 (04) : 799 - 809
[8] HUSSIN, 1997, INFORM PROCESS LETT, V63, P63
[9] Korte B, 1978, ANN DISCRETE MATH, V2, P65, DOI [10.1016/S0167-5060(08)70322-4, DOI 10.1016/S0167-5060(08)70322-4]
[10] Kosaraju S. R., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P166, DOI 10.1109/SFCS.1994.365696

← 1 →