Suppose we are given a graph with distances for each of the edges and merit for each of the nodes. What are the best (approximation) algorithms for computing the the most meritorious simple path with a cap on the maximum distance allowed?

  • 1
    $\begingroup$ Related: cstheory.stackexchange.com/q/25922/2150 $\endgroup$ Dec 26, 2014 at 8:45
  • 2
    $\begingroup$ Orienteering refers to the problem where one wants a walk with a given budget instead of a simple path - a node is allowed to be visited more than once but the merit/profit is only counted once. If distances satisfy triangle inequality then asking for a simple path is equivalent to asking for a walk. However, if you insist on a simple path then what you are looking for is closely related to the longest path problem. For longest paths check Gabow's paper and pointers: epubs.siam.org/doi/abs/10.1137/… $\endgroup$ Dec 27, 2014 at 4:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.