<p>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?</p>

CC BY-SA 3.0
2014-12-26T08:45:15.313Z
Related: http://cstheory.stackexchange.com/q/25922/2150
Marcus Ritt
CC BY-SA 3.0
2014-12-27T04:26:52.323Z
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: http://epubs.siam.org/doi/abs/10.1137/S0097539704445366?journalCode=smjcat
Chandra Chekuri
<approximation-algorithms><optimization><tsp>
Approximation Algorithm for TSP-like problem
ruadath
# Approximation Algorithm for TSP-like problem

(Asked by: username_0 on 2014-12-26)

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?

**Tags:** approximation-algorithms, optimization, tsp
> **Comments:**
> **username_1**: Related: http://cstheory.stackexchange.com/q/25922/2150  
> **username_2**: 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: http://epubs.siam.org/doi/abs/10.1137/S0097539704445366?journalCode=smjcat  

---

## 0 answers

