A problem related to routing in a graph

Question

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.

The new problem is this. There is a tourist who has a having the following information:

1. Time required to travel from one tourist spot to another.
2. A non negative number corresponding to each tourist spot. This number can be considered as the "attraction value" of the spot - higher the attraction value, the more preferable spot.

How should the tourist travel within a given time limit so that total attraction value is maximized?

This problem is different form Vehicle Routing Problems at least in one respect, the tourist need not visit all the spots. Moreover, the objective function does not depend on the edge weights as in most of the Vehicle routing problem.

Before attempting to design algorithm for this problem, I want to know if this problem is similar to some existing problem. Can anybody help?

Answer 1

The problem you describe is known as the Orienteering Problem (OP), see for example this survey (which takes an operations research viewpoint), and also this paper by Blum et al, which gives an efficient constant-factor approximation algorithm and shows that OP cannot be efficiently approximated better than some fixed constant unless P=NP (i.e. OP is APX-hard). Bansal et al. showed a 3-approximation.

There are some variants to the problem, and the simplest have to do with starting and ending points: you can specify a starting point (sometimes called rooted OP), or starting and ending points. The approximation algorithm by Bansal et al. above gives an efficient 3-approximation to the variant where you can specify both a starting and ending point: this implies a 3-approximation for the less constrained variants.