  In this paper a class of robust two-stage combinatorial optimization problems
is discussed. It is assumed that the uncertain second stage costs are specified
in the form of a convex uncertainty set, in particular polyhedral or
ellipsoidal ones. It is shown that the robust two-stage versions of basic
network and selection problems are NP-hard, even in a very restrictive cases.
Some exact and approximation algorithms for the general problem are
constructed. Polynomial and approximation algorithms for the robust two-stage
versions of basic problems, such as the selection and shortest path problems,
are also provided.
