title: Is there an algorithm to find the optimal value of k-tsp (traveling salesman) in polynomial time?
body: <p>I read <a href="http://www.springerlink.com/content/k66q7204vr21522t/" rel="nofollow">this</a> 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 <code>cost&lt;X</code> 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.</p>
  
  <p>I am interested in this for learning purposes,</p>
  
  <p>Any help/links would be appreciated.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>I am referring to finding the value of the optimal solution and not about finding the solution itself. </p>