Return to Answer

The problem you describe is known as the Orienteering Problem (OP), see for example this survey (which is takes an operations research viewpoint), and also this paper by Blum et al, which gives a constant-factor approximation algorithm and shows that OP cannot be approximated better than some fixed constant (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 a 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.

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.

The problem you describe is known as the Orienteering Problem (OP), see for example this survey (which is takes an operations research viewpoint), and also this paper by Blum et al, which gives a constant-factor approximation algorithm and shows that OP cannot be approximated better than some fixed constant (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 problem you describe is known as the Orienteering Problem (OP), see for example this survey (which is takes an operations research viewpoint), and also this paper by Blum et al, which gives a constant-factor approximation algorithm and shows that OP cannot be approximated better than some fixed constant (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 a 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.

The problem you describe is known as the Orienteering Problem, see for example this survey, and also this paper by Blum et al.

The problem you describe is known as the Orienteering Problem (OP), see for example this survey (which is takes an operations research viewpoint), and also this paper by Blum et al, which gives a constant-factor approximation algorithm and shows that OP cannot be approximated better than some fixed constant (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.