{'fraction_non_alphanumeric': 0.01818181818181818, 'fraction_numerical': 0.0, 'mean_word_length': 5.401162790697675, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Complexity of the Stochastic Fleet Assignment Problem

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 the past has decreasing predictive power for planning and deciding. Yet, researches 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. Nevertheless, 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. In this paper we show new hardness results for the deterministic fleet assignment problem, and the main result is that the stochastic variant of the fleet assignment problem is PSPACE-complete.