  In this paper the minmax (regret) versions of some basic polynomially
solvable deterministic network problems are discussed. It is shown that if the
number of scenarios is unbounded, then the problems under consideration are not
approximable within $\log^{1-\epsilon} K$ for any $\epsilon>0$ unless NP
$\subseteq$ DTIME$(n^{\mathrm{poly} \log n})$, where $K$ is the number of
scenarios.
