Vol 1 No 1 (2006)
Articles

On the Stability of Approximation for Hamiltonian Path Problems

Luca Forlizzi
Dipartimento di Informatica, Università di L’Aquila, I-67010 L’Aquila, Italy
Juraj Hromkovič
Department Informatik, ETH Zentrum, CH-8092, Zürich, Switzerland
Guido Proietti
Dipartimento di Informatica, Università di L’Aquila, I-67010 L’Aquila, Italy; Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, CNR, Roma, Italy
Sebastian Seibert
Department Informatik, ETH Zentrum, CH-8092, Zürich, Switzerland
Published January 24, 2006
How to Cite
Forlizzi, L., Hromkovič, J., Proietti, G., & Seibert, S. (2006). On the Stability of Approximation for Hamiltonian Path Problems. Algorithmic Operations Research, 1(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/95

Abstract

We consider the problem of finding a cheapest Hamiltonian path of a complete graph satisfying a relaxed triangle inequality, i.e., such that for some parameter β > 1, the edge costs satisfy the inequality c({x, y}) ≤β (c({x, z}) + c({z, y})) for every triple of vertices x, y, z. There are three variants of this problem, depending on the number of prespecified endpoints: zero, one, or two. For metric graphs there exist approximation algorithms, with approximation ratio 3/2 for the first two variants and 5/3 for the latter one. Using results on the approximability of the Travelling Salesman Problem with input graphs satisfying the relaxed triangle inequality, we obtain for our problem approximation algorithms with ratio in(β 2 + β,3/2 β 2) for zero or one respecified endpoints, and 5/3 β2 for two endpoints.