๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximation algorithms for the Euclidean bipartite TSP

โœ Scribed by Andreas Baltz; Anand Srivastav

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
214 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

โœฆ Synopsis

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worstcase examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average case behavior indicated by computational experiments.

๐Ÿ“œ SIMILAR VOLUMES

A 78-approximation algorithm for metric
A 78-approximation algorithm for metric Max TSP
โœ Refael Hassin; Shlomi Rubinstein ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 66 KB

We present a randomized approximation algorithm for the metric version of undirected Max TSP. Its expected performance guarantee approaches 7 8 as n โ†’ โˆž, where n is the number of vertices in the graph.

An approximation algorithm for a bottlen
An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane
โœ Lusheng Wang; Zimao Li ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 95 KB

We study a bottleneck Steiner tree problem: given a set P = {p 1 , p 2 , . . . , p n } of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in