Approximation algorithms for orienteering and discounted-reward TSP

By Avrim Blum, S. Chawla, David R Karger, Terran Lane, Adam Meyerson, Maria Minkoff. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., 2003

312 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Planning algorithms (2006, unknown): “For discrete environments, approximation algorithms for the problem of optimally visiting all states in a goal set (the orienteering problem) are presented and analyzed in [117, 190].”
Sensor planning for a symbiotic UAV and UGV system for precision agriculture (2013, unknown): “[12] presented a 4-approximation to the orienteering problem for complete graphs with metric edges.”
A survey on algorithmic approaches for solving tourist trip design problems (2014, methodology): “In their approach they show that a ( 2 + (cid:2)) -approximation to the min-excess ( s − t ) path problem can be used to obtain a 3-approximation for the OP, hence, improving the previous result by Blum et al. (2003, 2007).”
Robust Submodular Observation Selection (2008, background): “…the formalism developed in this section also allows to handle robust versions of combinatorial optimization problems such as the Knapsack (cf., Martello and Toth, 1990), Orienteering (cf., Laporte and Martello, 1990; Blum et al., 2003) and Budgeted Steiner Tree (cf., Johnson et al., 2000) problems.”
Efficient Informative Sensing using Multiple Robots (2014, methodology): “The above theorem and proof is inspired by the proof of multi-path orienteering provided by Blum et al. (2003). Lemma 3.”