  We consider a problem of placing generators of rewards to be collected by
randomly moving agents in a network. In many settings, the precise mobility
pattern may be one of several possible, based on parameters outside our
control, such as weather conditions. The placement should be robust to this
uncertainty, to gain a competent total reward across possible networks. To
study such scenarios, we introduce the Robust Reward Placement problem (RRP).
Agents move randomly by a Markovian Mobility Model with a predetermined set of
locations whose connectivity is chosen adversarially from a known set $\Pi$ of
candidates. We aim to select a set of reward states within a budget that
maximizes the minimum ratio, among all candidates in $\Pi$, of the collected
total reward over the optimal collectable reward under the same candidate. We
prove that RRP is NP-hard and inapproximable, and develop $\Psi$-Saturate, a
pseudo-polynomial time algorithm that achieves an $\epsilon$-additive
approximation by exceeding the budget constraint by a factor that scales as
$O(\ln |\Pi|/\epsilon)$. In addition, we present several heuristics, most
prominently one inspired by a dynamic programming algorithm for the max-min 0-1
KNAPSACK problem. We corroborate our theoretical analysis with an experimental
evaluation on synthetic and real data.
