𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Differential approximation results for the traveling salesman and related problems

✍ Scribed by Jérôme Monnot

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
90 KB
Volume
82
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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 idea improves this ratio to 3/4 and we obtain a differential nonapproximation threshold equal to 741/742. Remark that the 3/4-differential approximation result has been recently proved by a way more specific to the 1-, 2-case and with another algorithm in the recent conference, Symposium on Fundamentals of Computation Theory, 2001. Based upon these results, we establish new bounds for standard ratio: 5/6 for Max TSP[a, 2a] and 7/8 for Max TSP [1,2]. We also derive some approximation results on partition graph problems by paths.

📜 SIMILAR VOLUMES

Approximation algorithms for the capacit
Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries
✍ Shoshana Anily; Julien Bramel 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). This problem is characterized by a set of n pickup points and a set of n delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited

Differential approximation results for t
Differential approximation results for the Steiner tree problem
✍ M Demange; J Monnot; V.Th Paschos 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 654 KB

we study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than IV \ Nj-' for any E E (0, l), where V and N are the vertex-set of the input graph and the set of term