tailieunhanh - Approximation results toward nearest neighbor heuristic

In this paper, we revisit the famous heuristic called nearest neighbor (N N) for the traveling salesman problem under maximization and minimization goal. We deal with variants where the edge costs belong to interval [a;ta] for a>0 and t>1, which certainly corresponds to practical cases of these problems. | Yugoslav Journal of Operations Research 12 (2002), Number 1, 11-16 APPROXIMATION RESULT RESULTS S TOWARD NEAREST NEI NEIGHBOR GHBOR HEURISTIC J›rÚme MONNOT LAMSADE, Universit› Paris-Dauphine, Paris, France monnot@ Abstract: In this paper, we revisit the famous heuristic called nearest neighbor ( N N ) for the traveling salesman problem under maximization and minimization goal. We deal with variants where the edge costs belong to interval [ a; ta] for a > 0 and t > 1 , which certainly corresponds to practical cases of these problems. We prove that NN is a (t + 1) / 2t -approximation for max TSP [ a; ta] and a 2 /( t + 1) -approximation for min TSP [ a; ta] under the standard performance ratio. Moreover, we show that these ratios are tight for some instances. Keywords: Approximate algorithms, performance ratio, analysis of algorithms, traveling salesman problem. 1. INTRODUCTION The classical traveling salesman problem can be formulated as follows: given K n , a complete graph on n vertices with non-negative integer costs on its edges, the traveling salesman problem under minimization version, called min TSP (resp. maximization, called max TSP ) consists of minimizing (resp. maximizing) the cost of a Hamiltonian cycle, the cost of such cycle is the sum of its edge's costs. Moreover, when the edge-weights are in the set {a, a + 1,., b − 1, b} , we will call of TSP [ a; b] problem. Several restrictions of this problem have often been studied in the literature, like Euclidean, metric or 1, 2 cases and very elegant positive or negative approximation results have being produced by Arora [1], Christofides [2], Papadimitriou and Yannakakis [7], Engebretsen and Karpinski [3], Papadimitriou and Vempala [6]. There are no special studies about this heuristic when edge-weights are in the set {a, a + 1,., b − 1, b} . 12 J. Monnot / Approximation Results Toward Nearest Neighbor Heuristic In this paper, we revisit some approximation results for .