  We consider the pull-based broadcast scheduling model. In this model, there
are n unit-sized pages of information available at the server. Requests arrive
over time at the server asking for a specific page. When the server transmits a
page, all outstanding requests for the page are simultaneously satisfied, and
this is what distinguishes broadcast scheduling from the standard scheduling
setting where each job must be processed separately by the server. Broadcast
scheduling has received a considerable amount of attention due to the
algorithmic challenges that it gives in addition to its applications in
multicast systems and wireless and LAN networks. In this paper, we give the
following new approximation results for two popular objectives:
  - For the objective of minimizing the maximum flow time, we give the first
PTAS. Previously, it was known that the algorithm First-In-First-Out (FIFO) is
a 2-approximation, and it is tight. It has been suggested as an open problem to
obtain a better approximation.
  - For the objective of maximizing the throughput, we give a
0.7759-approximation which improves upon the previous best known
0.75-approximation.
  Our improved results are enabled by our novel rounding schemes and linear
programming which can effectively reduce congestion in schedule which is often
the main bottleneck in designing scheduling algorithms based on linear
programming. We believe that our algorithmic ideas and techniques could be of
potential use for other scheduling problems.
