Stochastic Airline Fleet Assignment is PSPACE-complete

In recent years, optimization under the assumption that input data is not completely available at decision time has received an increasing attention. The reason is that our world seems to become increasingly dynamic, such that data from past have decreasing predictive power for planning and deciding. esearchers have mainly concentrated on simple settings where the deterministic variant of a problem can be approximated in polynomial time, respectively on non-integer problems. Large multi-stage stochastic integer problems, induced from deterministic NP-hard problems that cannot be approximated, have rarely been examined. heless, these problems are motivated directly from practice. One very interesting and edge-leading example of this problem class is the Stochastic Fleet-Assignment-Problem which we examine in this paper. The main result of this paper is that the stochastic variant of the fleet assignment problem is PSPACE-complete. We build fleet assignment instances from stochastic SAT instances in order to show SSAT ≤p SFAP.