✦ LIBER ✦

On two geometric problems related to the travelling salesman problem

✍ Scribed by Christos H Papadimitriou; Umesh V Vazirani

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 739 KB
Volume: 5
Category: Article
ISSN: 0196-6774
DOI: 10.1016/0196-6774(84)90029-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on the traveling salesman problem

✍ V. Chvátal 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 85 KB

A two-dimensional mapping for the travel

A two-dimensional mapping for the traveling salesman problem

✍ S. Tsubakitani; J.R. Evans 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 477 KB

Transformation of multidepot multisalesm

Transformation of multidepot multisalesmen problem to the standard travelling salesman problem

✍ Yang GuoXing 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 300 KB

On a solution of the travelling salesman

On a solution of the travelling salesman problem

✍ L.A. Pchelintsev 📂 Article 📅 1966 🏛 Elsevier Science ⚖ 263 KB

On the solutions of stochastic traveling

On the solutions of stochastic traveling salesman problems

✍ Timo Leipälä 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 597 KB

Differential approximation results for t

Differential approximation results for the traveling salesman and related problems

✍ Jérôme Monnot 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 90 KB

This paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and cannot be differential approximable greater than 649/650. Next, we demonstrate that, when dealing with edge-costs 1 and 2, the same algorithm ide