Before revision: The model of streaming algorithms is motivated by the increasingly common situation in which the sheer amount of available data limits the ways in which the data can be accessed. Streaming algorithms are typically allowed a single pass over the data and can only store a sublinear fraction of the data at any time. We initiate the study of classic online selection problems\dots in a streaming model where the data stream consists of two parts: historical data points that an algorithm can use to learn something about the input;
After revision: A prophet inequality states, for some \alpha\in[0,1], that the expected value achievable by a gambler who sequentially observes random variables X_1,\dots in a streaming model where the data stream consists of two parts: historical data points that an algorithm can use to learn something about the input;