Approximation algorithms for the maximum Hamiltonian Path Problem with specified endpoint(s)

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]