The approximation ratio of the greedy algorithm for the metric traveling salesman problem

被引：7

作者：

Brecklinghaus, Judith ^{[1
]}

Hougardy, Stefan ^{[1
]}

机构：

[1] Univ Bonn, Res Inst Discrete Math, D-53113 Bonn, Germany

来源：

OPERATIONS RESEARCH LETTERS | 2015年 / 43卷 / 03期

关键词：

Traveling salesman problem; Greedy algorithm; Clarke-Wright savings heuristic; Approximation algorithm;

D O I：

10.1016/j.orl.2015.02.009

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is Theta (log n). Moreover, we prove that the same result also holds for graphic, euclidean, and rectilinear instances of the Traveling Salesman Problem. Finally we show that the approximation ratio of the Clarke-Wright savings heuristic for the metric Traveling Salesman Problem is (9 (log n). (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：259 / 261

页数：3

共 7 条

[1]

[Anonymous], 1972, Complexity of Computer Computations, DOI [10.1007/978-3-540-68279-0-8, DOI 10.1007/978-1-4684-2001-2]

[2] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[3]

Frieze A. M., 1978, OPER RES VERFAHREN, V32, P93

[4]

Hougardy Stefan, 2014, DISCRETE APPL MATH

[5] On the nearest neighbor rule for the traveling salesman problem [J].

Hurkens, CAJ ;

Woeginger, GJ .

OPERATIONS RESEARCH LETTERS, 2004, 32 (01) :1-4

[6] WORST-CASE ANALYSIS OF 2 TRAVELING SALESMAN HEURISTICS [J].

ONG, HL ;

MOORE, JB .

OPERATIONS RESEARCH LETTERS, 1984, 2 (06) :273-277

[7]

Reinelt, 1994, TRAVELING SALESMAN

← 1 →