On the maximum quadratic assignment problem
Viswanath Nagarajan, Maxim Sviridenko
SODA 2009
In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log log B)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n log B)-approximation algorithm; here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding "adaptivity gaps".
Viswanath Nagarajan, Maxim Sviridenko
SODA 2009
Viswanath Nagarajan, R. Ravi
Algorithmica (New York)
Joel Wolf, Zubair Nabi, et al.
Middleware 2014
Anupam Gupta, Moritz Hardt, et al.
SIAM Journal on Computing