2014/12/21 by Tobias Mömke, Mömke, Tobias
Computer Science · Engineering · #05C45 #05C85 #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems #Vehicle Routing Optimization Methods #acm:05C45 #acm:05C85 #cs.DS #msc:05C45 #msc:05C85
paper · pdf · doi:10.48550/arxiv.1412.6755
8 pages, 1 figure
arxiv created 2014/12/21 · openalex publication_date 2014/12/21 · arxiv updated 2014/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 beta2/4)-approximation algorithm for TSP with beta-relaxed triangle inequality (beta-TSP), where beta >= 1. A graph G is an instance of beta-TSP, if it is a complete graph with non-negative edge weights that are restricted as follows. For each triple of vertices u,v,w in V(G), c(u,v) <= beta (c(u,w) + c(w,v)).