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 HPPs,t if the two endpoints are specified, HPPs if only one endpoint is specified. We show that HPPs,t is 1/2-differential approximable and HPPs is 2/3-differentiable approximable. Moreover, we observe that these problems cannot be differential approximable better than 741/742. Based upon these results, we obtain new bounds for standard ratio: a 1/2-standard approximation for MAX HPPs,t and a 2/3 for MAX HPPs, which can be improved to 2/3 for MAX HPPs,t[a,2a] (all the edge weights are within an interval [a,2a], to 5/6 for MAX HPPs[a,2a] and to 2/3 for MIN HPPs,t[a,2a], to 3/4 for MIN HPPs[a,2a].