On the power and limitations of affine policies in two-stage adaptive optimization (Q715068)

A two-stage adaptive linear optimization problem is considered under right hand side uncertainty. The statement of the problem includes e.g., set covering, facility location, and Steiner trees problems as special cases. The problem statement is rather general, however it includes a restriction of non-negativity of the objective coefficients. The power and limitations of affine policies in solving adaptive optimization problems is considered, where the term ``affine policy'' means that the feasible region consists only of solutions in form of affine functions of the uncertain parameters. A tight characterization of the performance of affine policies is given: it can be a factor \(\Omega(m^{\frac{1}{2}-\delta})\) worse than full-adaptive solution for any \(\delta>0\), where \(m\) is the number of constraints. It is proved that the worst-case cost of the best affine policy is \(O(\sqrt{m})\) times the optimal cost when the first stage constraint matrix has non-negative coefficients. An \(O(\sqrt{m})\) approximation algorithm, which is not an affine policy , is presented without the assumption on non-negativity of the constraint coefficients.