کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428848 | 686943 | 2015 | 6 صفحه PDF | دانلود رایگان |
• Improved approximation algorithm for TSP with relaxed triangle inequality.
• Approximate Min. weight degree-4-bounded Eulerian subgraph of doubled complete graph.
• Application of degree bounded matroids, b-matchings, and a new orientation technique.
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β/4+3β2/4)(3β/4+3β2/4)-approximation algorithm for TSP with β-relaxed triangle inequality (β -TSP), where β≥1β≥1. A graph G is an instance of β -TSP, if it is a complete graph with edge weights c:E(G)→Q≥0c:E(G)→Q≥0 that are restricted as follows. For each triple of vertices u,v,w∈V(G)u,v,w∈V(G), c({u,v})≤β(c({u,w})+c({w,v}))c({u,v})≤β(c({u,w})+c({w,v})).
Journal: Information Processing Letters - Volume 115, Issue 11, November 2015, Pages 866–871