Consider a service utility where customers arrive over time, and the server is lazy and wants to serve customers with as little effort as possible. The server, however, cannot deny service to any arriving customer, and all customers have to be served that arrive before the closing time. Amid uncertainty of customer inter-arrival times, the server has to figure out the speed of service for each customer so as to minimize the overall effort. We will discuss very simple online algorithm with concrete guarantees on its performance even for the worst case customer inter-arrival times.
