Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty

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 optimization 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.

Automated summary

This paper discusses a class of robust two-stage combinatorial optimization problems, showing that the robust two-stage versions of basic network optimization and selection problems are NP-hard even in very restrictive cases. The paper constructs some exact and approximation algorithms for the general problem, as well as polynomial and approximation algorithms for robust two-stage versions of basic problems such as selection and shortest path problems.