  We consider a class of multi-stage robust covering problems, where additional
information is revealed about the problem instance in each stage, but the cost
of taking actions increases. The dilemma for the decision-maker is whether to
wait for additional information and risk the inflation, or to take early
actions to hedge against rising costs. We study the "k-robust" uncertainty
model: in each stage i = 0, 1,...,T, the algorithm is shown some subset of size
k_i that completely contains the eventual demands to be covered; here k_1 > k_2
>...> k_T which ensures increasing information over time. The goal is to
minimize the cost incurred in the worst-case possible sequence of revelations.
  For the multistage k-robust set cover problem, we give an O(log m + log
n)-approximation algorithm, nearly matching the \Omega(log n + log m/loglog m)
hardness of approximation even for T=2 stages. Moreover, our algorithm has a
useful "thrifty" property: it takes actions on just two stages. We show similar
thrifty algorithms for multi-stage k-robust Steiner tree, Steiner forest, and
minimum-cut. For these problems our approximation guarantees are O(min{T, log
n, log L_{max}), where L_{max} is the maximum inflation over all the stages. We
conjecture that these problems also admit O(1)-approximate thrifty algorithms.
