An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality

被引：7

作者：

Moemke, Tobias ^{[1
]}

机构：

[1] Univ Saarland, D-66123 Saarbrucken, Germany

来源：

INFORMATION PROCESSING LETTERS | 2015年 / 115卷 / 11期

关键词：

Algorithms; Analysis of algorithms; Approximation algorithms; Design of algorithms; Graph algorithms; Relaxed triangle inequality; TSP; PERFORMANCE GUARANTEES; TSP;

D O I：

10.1016/j.ipl.2015.06.003

中图分类号：

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

学科分类号：

0812 ;

摘要：

Given a complete edge-weighted graph G, we present a polynomial time algorithm to. compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weight of an optimal TSP solution of G. Based on this algorithm and a novel use of orientations, in graphs, we obtain a (3 beta/4 + 3 beta(2)/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an insfance of beta-TSP, if it is a complete graph with edge weights c: E(G) -> Q >= 0 that are restricted as follows. For each triple of vertices u, v, w is an element of V (G), c({u, v}) <= beta(c({u, w}) + c ({w, v})). (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：866 / 871

页数：6

共 15 条

[1] PERFORMANCE GUARANTEES FOR APPROXIMATION ALGORITHMS DEPENDING ON PARAMETRIZED TRIANGLE INEQUALITIES [J].