Minimizing the maximum flow time in batch scheduling

We consider the maximum flow time minimization problem in batch scheduling, which is a capacitated version of broadcast scheduling. In this setting, nn different pages of information are available at the server which receives requests from clients over time for specific pages. The server can transmit at most one page pp at each time to satisfy a batch of requests for the same page pp, up to a certain capacity BpBp. In this paper we give the first (1+ϵ)(1+ϵ)-approximations for this problem with arbitrarily small resource augmentation, using either more capacity or more speed.