
Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
Monnot, Jérôme (2005), Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), European Journal of Operational Research, 161, 3, p. 721-735. http://dx.doi.org/10.1016/j.ejor.2003.09.007
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
2005Nom de la revue
European Journal of Operational ResearchVolume
161Numéro
3Éditeur
Elsevier
Pages
721-735
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (EN)
This paper deals with the problem of constructing Hamiltonian paths of optimal weight, called HPPs,t if the two endpoints are specified, HPPs if only one endpoint is specified. We show that HPPs,t is Image -differential approximable and HPPs is Image -differential approximable. Moreover, we observe that these problems cannot be differential approximable better than Image . Based upon these results, we obtain new bounds for standard ratio: a Image -standard approximation for MImage HPPs,t and a Image for MImage HPPs, which can be improved to Image for MImage HPPs,t[a,2a] (all the edge weights are within an interval [a,2a]), to Image for MImage HPPs[a,2a] and to Image for MImage HPPs,t[a,2a], to Image for MImage HPPs[a,2a].Mots-clés
Hamiltonian paths; Analysis of algorithms; performance ratio; Combinatorial optimization; Complexity theory; differential ratio; Approximate algorithmsPublications associées
Affichage des éléments liés par titre et auteur.
-
Paschos, Vangelis; Monnot, Jérôme; Toulouse, Sophie (2003) Article accepté pour publication ou publié
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2004) Article accepté pour publication ou publié
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, S. (2003) Article accepté pour publication ou publié
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2001) Communication / Conférence