Is there an algorithm to find the optimal value of k-tsp (traveling salesman) in polynomial time?

I read this article, it suggests (page 1025 last paragraph) that there is a polynomial time algorithm to find the optimum of a k-tsp problem using binary search. Using binary search would suggest there exists an algorithm for checking if a solution exists with cost<X and this algorithm is used for the binary search. I 'googled' around for this and the only algorithm i could find was a non deterministic one (which is pretty trivial), but obviously i'm looking for a deterministic one.

I am interested in this for learning purposes,

Any help/links would be appreciated.

EDIT

I am referring to finding the value of the optimal solution and not about finding the solution itself.

Since TSP is a special case of k-TSP where k = number of nodes in the graph. If you had a solution for "what's the cheapest k-TSP route" in polynomial in relation to graph size, then you'd have a polynomial solution to decision problem version of TSP which would imply that P = NP.

So the answer is no. Deterministic polynomial algorithm for both decision problem and optimization version (they're essentially the same) of k-TSP doesn't exist (yet).