Catch them if you can
Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski · 2013
Consider the following problem of serving impatient users: we are given a set of customers we would like to serve. We can serve at most one customer in each time step (getting value vi for serving customer i). At the end of each time step, each as-yet-unserved customer i leaves the system independently with probability qi, never to return. What strategy should we use to serve customers to maximize the expected value collected?