On the Stability of Approximation for Hamiltonian Path Problems

Authors

  • 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

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.

Downloads

Published

2006-01-24

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

Issue

Vol. 1 No. 1 (2006)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.