Treffer: Approximation algorithms for the maximum Hamiltonian Path Problem with specified endpoint(s)
Title:
Approximation algorithms for the maximum Hamiltonian Path Problem with specified endpoint(s)
Authors:
Contributors:
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Source:
European Journal of Operational Research. 161:721-735
Publisher Information:
CCSD; Elsevier, 2005.
Publication Year:
2005
Collection:
collection:CNRS
collection:UNIV-DAUPHINE
collection:LAMSADE-DAUPHINE
collection:TDS-MACS
collection:PSL
collection:UNIV-DAUPHINE-PSL
collection:UNIV-DAUPHINE
collection:LAMSADE-DAUPHINE
collection:TDS-MACS
collection:PSL
collection:UNIV-DAUPHINE-PSL
Subject Terms:
Original Identifier:
HAL: hal-00004071
Document Type:
Zeitschrift
article<br />Journal articles
Language:
English
ISSN:
0377-2217
1872-6860
1872-6860
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.00004071v1
Database:
HAL
Weitere Informationen
This paper deals with the problem of constructing Hamiltonian paths of optimal weight, called HPP_s,t if the two endpoints are specified, HPP_s if only one endpoint is specified. We show that HPP_s,t is 1/2-differential approximable and HPP_s is 2/3-differential approximable. Moreover, we observe that these problems can not be differential approximable better than 741/742. Based upon these results, we obtain new bounds for standard ratio: a1/2-standard approximation for Max HPP_s,t and a 2/3 for Max HPP_s, which can be improved to 2/3 for Max HPP_s,t[a,2a] (all the edge weights are within an interval [a,2a]), to 5/6 for Max HPP_s[a,2a] and to 2/3 for Min HPP_s,t[a,2a], to 3/4 for Min HPP_s[a,2a].