Polynomial-Time Approximation Scheme for Data~Broadcast
Claire Kenyon
Nicolas Schabanel
Neal Young
The data broadcast problem is to find a schedule for broadcasting a given set of messages over multiple channels. The goal is to minimize the cost of the broadcast plus the expected response time to clients who periodically and probabilistically tune in to wait for particular messages. The problem models disseminating data to clients in asymmetric communication environments, where there is a much larger capacity from the information source to the clients than in the reverse direction. Examples include satellites, cable TV, internet broadcast, and mobile phones. Such environments favor the ``push-based'' model where the server broadcasts (pushes) its information on the communication medium and multiple clients simultaneously retrieve the specific information of individual interest. This sort of environment motivates the study of ``broadcast disks'' in Information Systems \cite{A98,BC96}. In this paper we present the first polynomial-time approximation scheme for the data broadcast problem for the case when $W=O(1)$ and each message has arbitrary probability, unit length and bounded cost. The best previous polynomial-time approximation algorithm for this case has a performance ratio of $9/8$ \cite{BBNS98}.
PTAS-STOC2k-Final.tex
%Last updated by Nicolas Fev 16
\documentclass{acmproc-sp}%[letter,10pt,twocolumn]{article}

\usepackage{fullpage}
\usepackage{amsmath,latexsym,amssymb}
\usepackage{array}
\usepackage{theorem}
%\usepackage[dvips]{epsfig}

\usepackage{algorithm}
\usepackage[noend]{algorithmic}
    \renewcommand{\algorithmiccomment}[1]{\quad \textit{// #1}}
    \renewcommand{\algorithmicrequire}{\textbf{Input:}}
    \renewcommand{\algorithmicensure}[1]{\textbf{Output:}}
    %\setboolean{ALC@noend}{true}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Polynomial-Time Approximation Scheme for Data~Broadcast}

\author{
  Claire Kenyon
  \and    Nicolas Schabanel
  \and    Neal Young
}
\date{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\theoremstyle{plain}

\theoremheaderfont{\normalfont\bfseries}
\theorembodyfont{\normalfont\itshape}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}

%\theoremheaderfont{\normalfont\itshape}
\theorembodyfont{\normalfont}
\newtheorem{definition}{Definition}
\newtheorem{notation}{Notation}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem{example}{Example}
\newtheorem{assumption}{Assumption}

%\newenvironment{proof}{
%    \paragraph{\normalfont\bfseries Proof.}
%} { %\hfill 
%    $\Box$
%    \smallskip
%}

\newenvironment{proofOf}[1]{
    \paragraph*{\quad\normalfont\scshape Proof of {#1}}
} { %\hfill 
    $\Box$
    \smallskip
}

\newenvironment{proofSketch}{
    \paragraph*{\quad\normalfont\scshape Proof sketch}
} { %\hfill 
    $\Box$
    \smallskip
}

\newenvironment{proofSketchOf}[1]{
    \paragraph*{\quad\normalfont\scshape Proof sketch of {#1}}
} { %\hfill 
    $\Box$
    \smallskip
}

\newcommand{\paragraphtitle}[1]{\noindent {\itshape #1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\inputfig}[1]{\hfill \input{#1.pstex_t} \hfill}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\renewcommand{\em}[1]{\textit{#1}}
\renewcommand{\th}{{\ensuremath{^{\text{th}}}}}
\newcommand{\st}{{\ensuremath{^{\text{st}}}}}
\newcommand{\nd}{{\ensuremath{^{\text{nd}}}}}

\newcommand{\ie}{\textit{i.e.}}
\newcommand{\IFF}{\textit{iff}}
\newcommand{\eg}{\textit{e.g.}}
\newcommand{\WLOG}{\textit{w.l.o.g.}}
\newcommand{\wLOG}{\textit{W.l.o.g.}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\DS}{\displaystyle}
\newcommand{\CD}{\ensuremath\centerdot}

\newcommand{\CC}{\ensuremath{\mathcal C}}
\newcommand{\event}{\ensuremath{\mathcal E}}

\newcommand{\eqdef}{\ensuremath{=_{\text{\normalfont def}}}}

\newcommand{\series}[4]{{\ensuremath{{#1}_{#2}{#4}\ldots{#4}{#1}_{#3}}}}
\newcommand{\cseries}[4]{\ensuremath{{#1}_{#2}{#4}\cdots{#4}{#1}_{#3}}}
\newcommand{\setseries}[2]{\ensuremath{\{{#1},\ldots,{#2}\}}}
\newcommand{\expect}{\ensuremath{\operatorname{\mathbb E}}}
\newcommand{\subst}[2]{\ensuremath{[{^{#1}\!\!/\!\!_{#2}}]}}
\newcommand{\lrsubst}[2]{\ensuremath{\left[{^{#1}\!\!/\!\!_{#2}}\right]}}

\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\newcommand{\LB}{\ensuremath{\operatorname{LB}}}
\newcommand{\LBNoC}{\ensuremath{
        \operatorname{LB_{\operatorname{no\,cost}}}}}
\newcommand{\dLB}{\ensuremath{\dot{\operatorname{LB}}}}
\newcommand{\ART}{\ensuremath{\operatorname{ERT}}}
\newcommand{\COST}{\ensuremath{\operatorname{COST}}}
\newcommand{\BC}{\ensuremath{\operatorname{BC}}}
\newcommand{\AVG}{\ensuremath{\operatorname{Avg}}}
\newcommand{\art}{{expected response time}}
\newcommand{\OPT}{\ensuremath{\operatorname{OPT}}}

\newcommand{\Gjk}{\ensuremath{G_{j,k}}}
\newcommand{\gjk}{\ensuremath{g_{j,k}}}

\newcommand{\dP}{{\ensuremath{\dot p}}}
\newcommand{\dC}{{\ensuremath{\dot c}}}
\newcommand{\dS}{{\ensuremath{\dot S}}}
\newcommand{\dM}{{\ensuremath{\dot M}}}

\newcommand{\halpha}{\ensuremath{\hat\alpha}}
\newcommand{\hS}{\ensuremath{\hat S}}

\newcommand{\NP}{\ensuremath{N\!P}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\long\def\unexpandedwrite#1#2{\def\finwrite{\write#1}%
%       {\aftergroup\finwrite\aftergroup{\sanitize#2\endsanity}}}
%\def\sanitize{\futurelet\next\sanswitch}
%\def\sanswitch{\let\n@xt\endsanity \ifx\next\endsanity
%       \else\ifcat\noexpand\next\stoken\aftergroup\space\let\n@xt=\eat
%       \else\ifcat\noexpand\next\bgroup\aftergroup{\let\n@xt=\eat
%       \else\ifcat\noexpand\next\egroup\aftergroup}\let\n@xt=\eat
%       \else\let\n@xt=\copytok\fi\fi\fi\fi \n@xt}
%\def\eat{\afterassignment\sanitize \let\next= }
%\long\def\copytok#1{\ifcat\noexpand#1\relax\aftergroup\noexpand\fi
%  \ifcat\noexpand#1\noexpand~\aftergroup\noexpand\fi
%  \aftergroup#1\sanitize}
%\def\endsanity\endsanity{}

%\newcommand{\proofDeferred}[2]{
%       (Deferred to Appendix)%
%       \unexpandedwrite15{%\subsection{Proof of #1}%
%                #2}
%}
%\newcommand{\flushProofDeferred}{
%       \immediate\closeout15
%       \input{proofs.deferred}
%}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\openout15=proofs.deferred

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%% TABLE OF CONTENTS

%\tableofcontents
%\listoffigures
%\listofalgorithms

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%  A B S T R A C T 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}\small
  The data broadcast problem is to find a schedule for broadcasting a given set
  of messages over multiple channels.  The goal is to minimize the cost of the
  broadcast plus the expected response time to clients who periodically and
  probabilistically tune in to wait for particular messages.
  
  The problem models disseminating data to clients in asymmetric communication
  environments, where there is a much larger capacity from the information
  source to the clients than in the reverse direction.  Examples include
  satellites, cable TV, internet broadcast, and mobile phones.  Such
  environments favor the ``push-based'' model where the server broadcasts
  (pushes) its information on the communication medium and multiple clients
  simultaneously retrieve the specific information of individual interest.
  This sort of environment motivates the study of ``broadcast disks'' in
  Information Systems \cite{A98,BC96}.
  
  In this paper we present the first polynomial-time approximation scheme for
  the data broadcast problem for the case when $W=O(1)$ and each message has
  arbitrary probability, unit length and bounded cost.  The best previous
  polynomial-time approximation algorithm for this case has a performance ratio
  of $9/8$ \cite{BBNS98}.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% I N T R O D U C T I O N
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Background and Result}
The input is a set $M=\{\series M1m,\}$ of messages, each with a probability
$p_i$ and cost $c_i$, and a parameter $W$ --- the number of channels.  The
output is (finitely described) infinite {\em broadcast schedule $S$} for the
messages --- specifying for each time $t=0,1,2,\ldots$ and channel $k$, a
message $S(t,k)$ (if any) to be broadcast at that time on that channel.  The
goal is to minimize the cost of the schedule, denoted $\COST(S)$ and defined as
the \emph{expected response time} plus the {\em broadcast cost} of $S$.

For a finite schedule $S$, the expected response time of $S$, denoted
$\ART(S)$, is defined as follows.  At each time unit, each message is requested
by some client with probability $p_i$.  Once a message is requested, the client
waits until the next time at which the message is scheduled on any channel (or
the end of the schedule, whichever comes first).  $\ART(S)$ is defined to be
the expected waiting time for a random request at a random time.  The broadcast
cost of $S$, denoted $\BC(S)$, is defined to be the total cost of scheduled
messages, divided by the length of the schedule.

Throughout the paper, if any real-valued function $f$ is defined with respect
to finite schedules, then we implicitly extend it to any infinite schedule $S$
as follows: $f(S) = \limsup_{n\rightarrow\infty} f(S_n)$, where $S_n$ denotes
$S$ restricted to the first $n$ time slots.  Thus, the above definitions of
expected response time and broadcast cost implicitly extend to infinite
schedules.  All of the infinite schedules considered in this paper will be
periodic, in which case this extension is particularly simple.

The data broadcast problem and special cases were studied in
\cite{A87,AW85,AW87,AGH98,BBNS98,G83,KS99,S00,VH97}.  Works studying 
applications and closely related problems include
\cite{A98,BC96,CC93,HW63,HR87,HMRTV89,IVB94,IR84,KL98,KZ98,S00,SL96,ST97,TX96,V94}.
Some of the above works study the generalization allowing messages to
have arbitrary lengths, which we do not consider here.

Ammar and Wong \cite{AW85,AW87} proved that there always exists an
optimal infinite schedule with finite period.  They also formulated a
natural relaxation of the problem that gives an explicit lower bound
on the optimum; the performance guarantee in this paper is proven with
respect to that lower bound.  More recently, constant-factor
polynomial-time approximation algorithms have been shown
\cite{AGH98,BBNS98}, the best to date being a $9/8$-approximation
\cite{BBNS98}.  Although the problem itself is not known to be
$\NP$-hard, several variants are known to be \cite{BBNS98,KS99,S00}.

Khanna and Zhou \cite[\S1.2]{KZ98} state that it is unknown whether the problem
is MAX-SNP hard, even when $W=1$ and without broadcast costs.  In this paper,
we show that it is not (unless P=NP).  We present the first deterministic
polynomial time approximation scheme for the problem, assuming the $W$ and each
cost is bounded by a constant.  By ``polynomial time'', we mean that the time
taken to output the finite description of the infinite schedule is polynomial
in the number of messages $m$ in the input.


\section{Summary of Approach}
Our algorithm is based on a simple new observation that works for a special
case of the problem.  We use fairly technical but to some extent standard
techniques to extend it to the general case.  We sketch the idea here,
glossing over a fair amount of technical detail.

Ammar and Wong \cite{AW85,AW87} relax the optimization problem by
allowing messages to (a) be scheduled at non-integer times and (b) to
{\em overlap}, while still insisting that the total {\em density} of
the scheduled messages is at most $W$, the number of channels (the
extension to the multiple channel case is due to~\cite{BBNS98}).  The
density of a message (or set of messages) is the total number of
scheduled times, divided by the length of the schedule.  Standard
calculus yields a solution to this relaxed problem.  The solution
specifies for each message $M_i$ a {\em density} $d^*_i$, meaning that
the message should be scheduled every $\tau^*_i = 1/d^*_i$ time units.

Ammar and Wong describe the following simple randomized rounding
algorithm for producing a real schedule: {\em For $t=1,2,\ldots$, for
$k=1\ldots W$, choose a single message $M_i$ randomly so that
$\Pr\{M_i \mbox{ selected}\}$ is $d^*_i/W=W/\tau^*_i$; schedule $M_i$
in schedule slot $S(t,k)$.}  They observe that the expected waiting
time for a random request for $M_i$ is essentially $\tau^*_i$ in this
schedule.  Since the expected waiting time in the relaxed schedule is
essentially $\tau^*_i/2$ (because an average request falls midway
between two successive broadcasts of $M_i$), this yields a
2-approximation w.r.t.\ expected response time. Since the expected
broadcast cost of $S$ is the same as the broadcast cost of the relaxed
solution, the algorithm is a $2$-approximation algorithm w.r.t.\ the
total cost.  Ammar and Wong also describe a greedy algorithm that
Bar-Noy, Bhatia, Naor and Schieber generalize in~\cite{BBNS98} to the
multiple channel case and prove to be essentially a derandomization of
the randomized algorithm, with the same performance guarantee.

\medskip\noindent {\bf Round-robin within groups.}  Since our goal is a PTAS,
we naturally group messages that are essentially equivalent (i.e.\ have
essentially the same cost and probability).  Our simple idea is the following
variation of Ammar and Wong's rounding scheme, which is most simply described
as follows: Schedule the messages as Ammar and Wong do, but then, {\em within
  each group, rearrange the messages so that they are scheduled in round-robin
  (cyclic) order.}  The broadcast cost is unchanged, but the expected response
time improves as follows.  Whereas before, a random request for a message $M$
in a group $G$ would have waited (in expectation) for $|G|$ messages from $G$
until finding its message, in the round-robin schedule, a random request for
$M$ will wait (by symmetry) for $(1+2+\cdots+|G|)/|G|) = (|G|+1)/2$ messages
from $G$.  That is, the expected wait in the round-robin schedule is
$(|G|+1)/(2|G|)$ times the expected wait in the Ammar-Wong schedule.  Since the
Ammar-Wong schedule has performance guarantee $2$, the round-robin schedule has
performance guarantee $\max_G (|G|+1)/|G| = 1 + 1/\min_G |G|$.  Thus, when the
groups are all large, the Ammar-Wong relaxation is essentially tight.

\medskip\noindent
{\bf Extending to the general case.}
Recall that for our purposes a group is a collection of messages
with approximately (w.r.t.\ $\epsilon$) the same probability and cost.
As long as each group has size at least $1/\epsilon$,
the round-robin schedule gives a $(1+\epsilon)$-approximation.

To extend to the general case, we show the following.
{\em Any} set of messages can be partitioned into three classes as follows:
%
\begin{enumerate}
\item[$A$] --- A constant number of {\em important} (high probability) messages.
\item[$B$] --- Messages belonging to {\em large groups}.
\item[$C$] --- Leftover messages, contributing {\em negligibly} to the cost.
\end{enumerate}
%
The basic intuition for the existence of this partition is that, due
to the rounding, the message-probabilities of the successive groups
decrease exponentially fast.  Thus, for all but a constant number of
groups (where the message-probability is high), either the group is
very large, or the total probability of the messages in the group is
very small.  Althouth the intuition is basic, obtaining the proof with
the appropriate parameters is is somewhat involved and delicate.

Once we have the partition, we proceed as follows:
\medskip
\\\noindent 1. Find the density $\alpha$ of messages in $A$ in a near-optimal
schedule of $A$ and $B$.
\\2. Compute an optimal ``short'' schedule $S_A$ of $A$ having density approximately $\alpha$.
\\3. Schedule the messages in $B$ in the slots not occupied by $A$,
using the group-round-robin algorithm.
\\4. ``Stretch'' the schedule, interspersing empty slots every $1/\epsilon$
time units, and schedule the messages for $C$ in these empty slots.
\medskip

Note that in order to ``cut and paste'' the schedules together, we have to
explicitly control the density of $A$ and $B$.  This in itself requires little
that is new.  The main new difficulty is the following.  In step 3, we are
using the round-robin algorithm to schedule $B$, but in a schedule that is
already partially filled by $A$.  For the analysis of the round-robin algorithm
to continue to approximately hold, we require that the empty slots in schedule
$S_A$ are sufficiently {\em evenly distributed} so that the scheduling of $B$
is not overly delayed at any time (cost increases quadratically with delay).

A-priori, imposing this additional requirement on $S_A$ might increase the cost
of $S_A$ too much.  To show that this is not the case, we show (using a
non-constructive probabilistic argument) that there is a schedule of $A$ that
has {\em constant-length period}, density approximately $\alpha$, and cost
approximately the cost of any optimal schedule of $A$ with density $\alpha$.
Since the period of this schedule is small, the empty slots are {\em necessarily}
evenly distributed.

The final output of the algorithm is a finite (size linear in the
input size) description from which an infinite schedule with
approximately optimal expected cost can be generated by a randomized
algorithm in an ``on-line'' fashion, where each step requires $O(W)$
time to schedule.

The running time of the various steps is as follows.  In step 1, only a
constant number of densities $\alpha$ need to be considered: we can try them
all and take the best.  For each $\alpha$, the time for the remaining steps is
as follows.  Step 2 can be done in constant time since the schedule we are
looking for has constant length.  Step 3 can be done in randomized time in the
size of the output.  Step 4 can also be done in randomized linear time in the
size of the output.

The final technical hurdle is showing that the algorithm can be
derandomized (extending the analysis of the greedy algorithm by
Bar-Noy, Bhatia, Naor and Schieber to this more complicated setting).
The resulting deterministic algorithm outputs a polynomial-length
schedule, the repetition of which gives the desired near-optimal
infinite schedule.

\iffalse
{\bf The techniques}. This is a rather technical
contribution to the area of approximation schemes, which uses
several usual techniques s.a. rounding, exhaustive search
 and treating ``large''
objects separately, but also requires a few additional ideas, specific to
this problem, which we now point out.
As in all previous papers since Ammar and
Wong's seminal work on the topic, we focus on the very informative
lower bound, in which one can separate the contribution of each
message to the objective function.
Since the lower bound is tight up
to a factor of 2, it  helps us identify the messages
which contribute a lot to the objective function and must be treated
with special care (``important'' messages). 
One apparently difficult case arises when there are
many messages of similar costs and probabilities, which individually
contribute very little to the objective function but are quite significant
as a group. One simple but important new idea is that the lower bound
is in fact essentially optimal in that case and is achieved
by a round-robin-type heuristic. 

Our algorithm thus starts by
classifying messages into three categories: first, a constant 
number of important messages (set $A$); second, messages belonging to
large groups (messages are grouped when they have the same
probability and cost); the other messages are negligible and can easily
be dealt with in the end.
Now, imagine that we guess the fraction of time which the optimal
schedule devotes to broadcasting messages from each category (or
{\em {density}} of each category). It seems that one could
construct the optimal schedule of the ``important'' messages $A$ with respect
to the density constraint, and then use the unoccupied time slots to
broadcast the messages from the second category using the round-robin-type
heuristic. However this is only provably efficient if one can
 relate the period  of the schedule of $A$
to the size of the groups of the second category. Studying the period
of an optimal schedule of $A$ requires a new
idea: cutting the schedule 
into pieces and glueing them back together in random order (with special
glue that prevents interactions between blocks) has a 
smoothing effect which enables us to prove that the period can
essentially be bounded by $|A|^2$. Furthermore,
a structural lemma, requiring some
further technical partitioning idea, proves that the groups can be assumed
to have size at least $\kappa |A|^2$ for any $\kappa$. This is the
key to the analysis of our approximation scheme.

{\bf Plan of the paper}. We construct the algorithm gradually.
After a preliminary section (Section \ref{sec:lb}) recalling the lower bound of
Ammar and Wong and extending it suitably, we present (Section 
\ref{sec:simplecase}) a simple
special case of message set (every message has many identical
sibling  messages), for which we combine
information from the lower bound with a round-robin type heuristic.
We then study (Section 
\ref{sec:criticalcase}) a slightly more general case of message set 
(every message,
except for a constant number, has many identical
sibling  messages); the proof of Lemma \ref{lem:boundedperiod} for bounding the period
of the schedule of the important messages contains a 
random-shuffling type argument. Section \ref{sec:negligible}  
explains how to deal with negligible
messages and  is
relatively straightforward. Section \ref{sec:PTAS} puts the ideas together
to construct a polynomial type randomized approximation scheme; its
validity rests on the structural Lemma \ref{lem:partition}; we then proceed to show
how the algorithm can be derandomized in a greedy fashion and how
the period of the resulting schedule can be controlled. Finally
in section \ref{sec:technical} we state several easy but useful 
lemmas which are used
in several of the other proofs.

\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% THE LOWER BOUND
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Group round robin}
\label{sec:lb}
\label{sec:simplecase}

Let the set of messages $M$ be partitioned into groups
$G_1,\ldots,G_q$ where group $G_j$ has size $g_j$  every message in $G_j$
has the same probability $p_j$ and broadcast cost $c_j$.
Let $\alpha$ be the desired maximum density of $M$ in the schedule.
In this notation, Ammar and Wong's relaxation of the problem is:
$$
\LB(M,\alpha) = \left\{
        \begin{array}{c}
        \DS\min_{\tau>0} \DS\sum_{j=1}^q \frac{p_j g_j^2 \tau_j}2 
                                + \frac{c_j}{\tau_j}\\
        \text{\normalfont Subject to:} ~
                 \DS\sum_{j=1}^q \frac1{\tau_j} \leq \alpha W
        \end{array}\right.
$$
                                %

\begin{lemma}[Lower Bound \cite{AW85}]
The minimization problem~$\LB(B,\alpha)$ is a lower bound to the contribution of the
messages of~$B$ to the cost of any schedule~$S$ over $W$~channels, in
which $B$~has density~$\leq\alpha$.

The problem has a unique solution~$\tau^*$ satsifying: $g_j
\tau^*_j=\sqrt{(2c_j+\lambda^*)/p_j}$, for some $\lambda^*\geq0$. If
$\sum_{j\in B} g_j \sqrt{p_j/(2c_j)} \leq \alpha W$, then $\lambda^* =0$;
otherwise, $\lambda^*$~is the unique solution to: $\sum_{j\in B}
\sqrt{p_j/(2c_j+\lambda^*)} = \alpha W$.
\end{lemma}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% A   I N T E R E S T I N G   C A S E 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
The following important observation states that {\WLOG} messages
from the same group can be scheduled in Round Robin order.
\begin{lemma}[Round Robin] \label{lem:roundrobin}
 For any
schedule~$S$, there exists a schedule~$S'$ in which the messages are
broadcast in Round Robin order within each group, so that: \\
\centerline{$
\COST(S') \leq \COST(S) .
$}\\
%and the inequality is strict if $S$ is periodic and different from $S'$.
\end{lemma}

\begin{proof}
In~$S$, consider a request for a message of~$G_j$, and the $|G_j|$~next
broadcasts of messages of $G_j$ after that request: the expected
response time to the request is minimized if all messages
of~$G_j$ are broadcast during those~$|G_j|$ time slots. Thus changing $S$
so as to reschedule the messages in~$G_j$ in Round Robin order, decreases the
expected response time while leaving the broadcast cost. Note that
if $S$~is periodic of period $T$, then the resulting schedule~$S'$ is also periodic and of period at most
$T\prod_j g_j$.
\end{proof}

%\subsection{Approximation for large groups}
The next step consists in observing that the lower bound
 is {\em tight} in the setting of this section.

According to the general lower bound, it is desired that a message 
is broadcast 
every $\tau^*_i g_i$, and then a random request for that
message would have to wait for about $\tau^*_i g_i /2$ on
average. In the algorithm of~\cite{BBNS98} (specialized to this setting), each
\emph{message}~$M_i$ is broadcast with probability~$1/(\tau^*_i g_i)$, 
so that any
request has to wait on average~$\tau^*_i g_i$ time: thus they obtain then a
$2$-approximation. 

On the other hand, in our Algorithm~\ref{algo:rando}, 
we schedule the
\emph{group}~$G_j$ with probability~$1/\tau^*_j$, and then the messages
in Round Robin order within the groups. Since a request for a
message in~$G_j$, has to wait with equal probability for the 1\st, the
2\nd,..., the $g_j\th$~broadcast of messages in~$G_j$, it will be
served after $\tau^*_j\cdot(g_j+1)/2$~expected time. We will thus
obtain  a $\min_i((g_i+1)/g_j)$-approximation, which is
a~$(1+\epsilon)$-approximation since all groups have size at least 
$1/\epsilon$. We believe that this simple idea might be applicable to
other problems.

\fi


\begin{lemma}[Randomized Approximation] \label{lem:rando}
In the setting of this section, the randomized
algorithm~\ref{algo:rando} constructs a one-channel schedule~$S$
whose cost satisfies:\\
\centerline{$
\expect[\COST(S)] = \DS{ \sum_{j=1}^q \left(
        p_j \frac{g_j(g_j+1)}2 \tau_j + \frac{c_j}{\tau_j}
        \right) - \frac12} $}\\
%
If $\tau$~is chosen in order to minimize~$\LB(M,1)$, then
algorithm~\ref{algo:rando} is a~$\max_j (1+1/g_j)$-approximation.
\end{lemma}

\begin{algorithm}[htb]
\caption{Group round-robin algorithm}\label{algo:rando}
\begin{algorithmic}
%\REQUIRE       A set messages partitioned into groups $\series G1q,$ 
%       of size $g_j$, and a set of reals $\tau_j>0$ so that $\sum_j
%       \tau_j \leq W$.
\IF{$\sum_{j=1}^q 1/\tau_j < 1$} 
        \STATE $\CD$ Add a dummy group~$G_0$
        with~$p_0=c_0=g_0=0$ and $1/\tau_0 = 1-\sum_{j=1}^q 1/\tau_j$.
\ENDIF
\FOR {$t=1..\infty$}
        \STATE $\CD$ Draw at random a group~$G_j$ with
        probability~$1/\tau_j$. Schedule in time slot~$t$, the next
        message of group $G_j$ in  Round Robin order, if $j\neq0$;
        and stay idle otherwise.
\ENDFOR
\end{algorithmic}
\end{algorithm}


\begin{proof}
A message of~$G_j$ is broadcast during a time slot with
probability~$1/\tau_j$, then the average density of the group~$G_j$
is then $1/\tau_j$. Then: $\expect[BC(S)]=\sum_j c_j/\tau_j$.\\
%
As explained above, a request for a message in~$G_j$ waits on average
$1/2$ until the end of the current time slot and then
$(g_j+1)/2$~broadcasts of a message in~$G_j$ on average. Then:
$\expect[\ART(S)]=\frac12+\sum_j p_j g_j \tau_j \frac{g_j+1}2$.\\
%
Finally if $\tau=\tau^*$, then since $\sum_j p_j g_j=1$ and
$\tau^*\geq1$, we get that: $\expect[\COST(S)] \leq
\sum_j(p_jg_j\frac{g_j+2}2\tau^*_j + c_j/\tau^*_j)$,
hence the claimed performance ratio.
\end{proof}

\begin{remark}
Note that the law of large numbers implies that the expected cost is
obtained with probability $1$.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% CRITICAL CASE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Scheduling {\large $\mathbf A$} and {\large $\mathbf B$}}
\label{sec:criticalcase}

Next we treat the case where the set of the messages~$M$ can be partitioned
into two sets~$A$ and~$B$ such that
\begin{itemize}
\item $A$ consists of a constant number of messages
\item $B$ is partitioned into groups as in the previous section,
such that each group has size at least $\kappa(\epsilon) |A|^2$, 
where $\kappa=\kappa(\epsilon)$~will be
defined later.
\end{itemize}

\iffalse
A key point is to remark that, if we know the 
 density of the messages of~$A$ in an optimal schedule, and if
we can schedule  the messages of~$A$ almost optimally
subject to this density constraint while keeping the period
of the schedule small, then we can complete the schedule
by scheduling the messages of~$B$ in the remaining empty slots
according to the randomized algorithm given above. Determining the
densities of~$A$ and~$B$ thus  allows  to treat those two sets of
messages independently.
\fi

Recall from the discussion in the introduction that the challenge
at this point is to show that there is a near-optimal schedule of $A$
with the appropriate density $\alpha$ and in which the empty slots
are relatively uniformly distributed.  If so, then we can find the desired
schedule for $A$ by exhaustive search, and then schedule $B$ into the empty
space in the schedule using the round-robin algorithm previously described.

To show the existence of the desired schedule for $A$, we show there is a
near-optimal schedule of $A$ with the appropriate density and with {\em
  constant period} (independent of $\alpha$).
\begin{lemma} \label{lem:boundedperiod}
Given a set of messages~$A$, with cost at most $\CC$, some
constant $0<\epsilon<1$ and a density~$0<\alpha<1$, there exists a
periodic schedule~$S$ satsifying:
\begin{enumerate}
\item   The density of empty slots is $S$ is approximately~$(1-\alpha)$:\\
%
$1-\alpha(S) \geq (1-\epsilon) (1-\alpha)$, ~and~
$\alpha(S)\in]0,1[$
%
\item   The cost of $S$ is approximately optimal:\\
\centerline{$\COST(S,A) \leq (1+\epsilon)\OPT(A,\alpha) + \epsilon/2$}
%
\item   The period $T_S$ of $S$ can be  bounded:\\
\centerline{$T_S\leq \cfrac{40 \ln (1+4/\epsilon)}{\epsilon^4(1-\epsilon/6)} \max(\CC,1)\cdot |A|^2$}
\end{enumerate}
\end{lemma}

\begin{proofSketch} 
Our proof uses the probabilistic method. The main new, simple idea, is
in the construction, which efficiently smoothes the cost function by
erasing its possible wide variations over time in the particular
schedule under study.

 Let~$T$ be a parameter to be determined later.  Let~$S^*$ be a periodic schedule of~$A$ with
 density~$\alpha$ and which is nearly optimal: basically,
 $\COST(S^*,A)\leq (1+\epsilon)\OPT(A,\alpha)$.  Let~$T^*$ denote the period
of~$S^*$, which w.l.o.g. is a multiple of $T$.

From~$S^*$, construct another periodic 
schedule~$S_2$ by inserting in~$S^*$, every $T$~steps from a random
starting point,
%o.w. the proof doesn't work
all the messages of~$A$ in a fixed order. $S_2$~is thus structured
into blocks of length~$T+|A|$. Let~$S_n$ be the random schedule
obtained by concatenating $n$~blocks chosen at random from~$S_2$. For
suitable values of~$T$ and~$n$, we can prove that with positive
probability, $S_n$~satisfies the first two statements of the
Lemma. The period of~$S_n$ is clearly~$n(T+|A|)$, which
together with the choice of $T$ gives the third
statement of the Lemma.
\end{proofSketch}

\begin{notation}
Let~$T(\epsilon) = \cfrac{40\ln (1+4/\epsilon)}
{\epsilon^4(1-\epsilon/6)} \max(\CC,1)$ denote the bound of the lemma for 
$\hbox{period}(S)/|A|^2$. Parameter $\kappa$ will be defined as~$\kappa(\epsilon)
\eqdef 2 W T(\epsilon)/\epsilon$.
\end{notation}

%\subsection{Building a nearly optimal schedule}

The algorithm for scheduling $A\cup B$ is given below, and is
an $\epsilon$-approximation for the cases studied in this section.
Since this is the critical case, the analysis is promoted
from a lemma to a proposition.
\begin{proposition} \label{pro:A+B}
Let $\epsilon < 1/7$. In the setting of this section,
 Algorithm~\ref{algo:A+B} yields a
schedule~$S$, such that: $$
\expect[\COST(S)] \leq (1+5\epsilon) \OPT(A\cup B)
$$
\end{proposition}

\begin{algorithm}[htb]
\caption{Scheduling~$A$ and~$B$} \label{algo:A+B}
\begin{algorithmic}
\FOR{$x=1..(W\cdot T(\epsilon)|A|^2-1)$} 
    \STATE $\CD$ Compute an optimal periodic schedule~$S_\alpha$
    of~$A$ with density~$\alpha= x/(W\cdot T(\epsilon) |A|^2)$ and
    period~$\leq T(\epsilon)|A|^2$.
\ENDFOR
\STATE  $\CD$ Choose $\alpha_0$ which minimizes:\\      
        \centerline{$\COST(S_{\alpha_0},A) + \LB(B,1-\alpha_0)$}
\STATE  $\CD$ Compute the $\tau^*$ that minimizes $\LB(B,1-\alpha_0)$;
        Add a dummy group~$G_0$ with $p_0=c_0=0$ and $\tau^*_0$, such
        that: $1/\tau^*_0 = (1-\alpha_0) W-\sum_{j\in B} 1/\tau^*_j$.
\ENSURE
\FOR{$t=1..\infty$}
        \STATE $\CD$ Schedule during time slot~$t$, the same
        messages of~$A$ on the same channels, as in~$S_{\alpha_0}$.
%  
        \FORALL{empty slot~$s$ during time slot~$t$} 
%
                \STATE $\CD$ Draw a group~$G_j$ of~$B$ with
                probability~$1/(\tau^*_j(1-\alpha_0) W)$. Schedule in
                slot~$s$, the next message of~$G_j$ in Round Robin
                order, if~$j\neq0$; and stay idle otherwise.
%
        \ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{proofSketch}
The proof works in two steps:
\begin{enumerate}
\item   \label{pf:stepANA1} Scheduling the messages of~$B$ with the 
randomized algorithm~\ref{algo:rando} in the empty slots achieves a
good approximation of $\COST(S_{\alpha_0},A)+\LB(B,1-\alpha_0)$ (Using
the mapping lemma~\ref{lem:mapping}).
%
\item   \label{pf:stepOPT1} $\COST(S_{\alpha_0},A)+\LB(B,1-\alpha_0)$ 
is a good approximation of the optimal cost (Using
Lemma~\ref{lem:boundedperiod}).
\end{enumerate}
\end{proofSketch}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% S C H E D U L I N G   N E G L I G E A B L E S 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{{\large $\mathbf C$} --- The negligible messages}
\label{sec:negligible}
In this section, to show how to incorporate the ``negligible'' messages into
the schedule.  We assume that the set of messages~$M$ is partitioned into two
sets~$AB$ and~$C$, where $C$ has a ``negligible contribution'' to the cost.
(This section can be skipped by the reader who is in a hurry).

\begin{definition} 
A subset of messages~$C\subseteq M$ has \emph{negligible contribution}
if its contribution to the lower bound is $O(\epsilon)$, when it is 
scheduled on one channel with density~$O(\epsilon/\CC)$, {\ie}:\\
\centerline{$\LB_{W=1}(C,\epsilon/(10\CC )) \leq 3\epsilon\OPT(M)/10$}
%
The constants~$1/10$ and~$3/10$ are arbitrary and are chosen in order
to improve readability in the following results.
\end{definition}

Basically, a subset of messages~$C$ is negligible if its
contribution to the cost is small, in the schedule
constructed by inserting its messages are
inserted from time to time (every $O(1/\epsilon )$ steps)
 into a schedule of the rest of the
messages.

\begin{lemma} \label{lem:scheduleC}
Consider a set of messages $M$, partitioned into two sets~$AB$
and~$C$, where $C$ has a negligible contribution to the cost. Then,
for any schedule~$S$ of~$AB$, one can construct in linear time a
random schedule~$S'$ of~$M$, such that: $$
\begin{array}{l}
\expect[\COST(S')] \\
~~~~~~~~~~~\leq (1+\frac{\epsilon}{10})\COST(S,AB)+ \frac{9\epsilon}{10}\OPT(M)
%\smallskip \\
%~~~\leq (1+\epsilon)\OPT(M) 
%\text{\normalfont, if $\COST(S,AB)\leq\OPT(M)$}
\end{array}
$$ 
%
If $\COST(S,AB)\leq\OPT(M)$, this is a $(1+\epsilon)$-approximation.
\end{lemma}

\begin{proof}
We first construct from $S$ another schedule $S_1$ of $AB$  by inserting 
an empty slot, on all the channels, every $10\CC/\epsilon-1$~slots,
starting at a random point in~$\{0,\ldots,10\CC/\epsilon-2\}$. The
stretching lemma~\ref{lem:stretching} ensures that:
$\expect[\COST(S_1)] \leq (1+\epsilon/10)\COST(S,AB)$. Let $\tau^*$ be
the solution to the minimization
problem~$\LB_{W=1}(C,\epsilon/(10\CC))$. We obtain~$S'$ by scheduling
the messages of~$C$ on  the {first} channel
in the empty slots of~$S_1$, according to the randomized 
algorithm~\ref{algo:rando}
with~$\tau=10\tau^*\CC/\epsilon$. Lemma~\ref{lem:rando} and the scaling
lemma~\ref{lem:scaling} ensure that the expected contribution of~$C$
is bounded by~$3\LB(C,\epsilon/(10\CC))\leq9\epsilon\OPT(M)/10$.
\end{proof}

\begin{remark}
The algorithm above can easily be derandomized by trying all the
starting point and choosing the one that minimizes the over cost for
the messages of~$AB$ and use the greedy algorithm~\ref{algo:greedy} to
schedule~$C$.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% T H E   P T A S
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{PTAS for Data Broadcast}
\label{sec:PTAS}
We now assume that we are in the general case.
The aim of the section is to prove the following theorem, which is the
main result of the paper. 
\begin{theorem}[PTAS] \label{thm:PTAS}
Given $\epsilon<1/7$ and a set~$M$ of messages, with message
costs bounded by $\CC$,  Algorithm~\ref{algo:PTAS} constructs in $O(m^2)$~time
a periodic schedule~$S$ with period~$\leq (m^2+m\max(1,\CC))/\epsilon$,
so that: $$
\COST(S)\leq (1+11\epsilon) \OPT(M)
$$
\end{theorem}
We will
first derive a PTRAS that will be derandomized in
Section~\ref{sec:derando}. 

\subsection{Randomized}
We now need to put together
the ideas developed for the special cases of the previous sections.
As a preliminary treatment, we use standard rounding techniques
to reduce the number of different messages.

%\marginpar{Could certainly be merged?}
%
%\begin{corollary}[PTAS2]
%Given $0<\epsilon<1/7$ and a set~$M$ of messages, with cost in bounded
%range~$[0,\CC]$, one can construct in $O(m^2)$~time a periodic
%schedule~$S$ of~$M$ with period~$\leq(m^2+m\max(1,\CC))/\epsilon$ and:$$
%\COST(S)\leq(1+11\epsilon)\OPT(M)
%$$
%\end{corollary}

%\begin{proof}
%As in the proof of Lemma~\ref{lem:boundedperiod}, we use the
%stretching lemma~\ref{lem:stretching} in order to cut
%deterministically the schedule generated by the PTAS, into independent
%blocks with length $\leq(m^2+m\max(1,\CC))/\epsilon$, and select the
%block with the smallest cost.
%\end{proof}

%\subsection{Partitioning}

\begin{lemma}[Rounding] \label{lem:rounding}
Without loss of generality, we can assume that the request
probabilities~$p_i$ are a multiple of powers of~$1/(1+\epsilon)$ and
the broadcast costs are multiples of~$\epsilon/W$:
\begin{eqnarray*}
p_i & = & r/(1+\epsilon)^j \text{, for some $j\geq 1$}\\ c_i & = &
k \cdot \epsilon/W \text{, for some $k\in\{0,\ldots, C\cdot
W/\epsilon\}$}
\end{eqnarray*}
where $1 < r \leq 1+\epsilon$.
\end{lemma}

\begin{proof}
Standard and omitted.
\end{proof}

%\begin{definition}[Grouping]
%We define $\Gjk$ as the \emph{group} of the messages with request
%probability $r/(1+\epsilon)^j$ and broadcast cost $k\epsilon/W$. Let
%$\gjk = |\Gjk|$.
%\end{definition}

The following lemma is the main tool for putting together the various
special cases studied so far, and is thus a key part of our construction.
We would like to claim that similar ideas could be applied to
other problems as well, however we were unable to abstract 
simple and general ideas from the technical proof. Perhaps, if one
believes that every approximation scheme rests on one ``structural lemma'',
 it can be seen as the structural lemma for this problem. 
\begin{lemma}[Partition] \label{lem:partition}
Given~$\epsilon>0$ and $\kappa>0$, one can construct, in linear time in
$m$, a partition of the groups~$(\Gjk)$, of messages with
probability~$r/(1+\epsilon)^j$ (where $r$ is the normalizing
constant such that $\sum_{\{j\geq1;k=0..\CC W/\epsilon\}}
r \gjk /(1+\epsilon)^j= 1$) and cost~$k\epsilon/W$, into three
sets~$A,B,C$ so that:
\begin{enumerate}
\item   The groups of $A$ have total size constant: 
$|A|\eqdef \sum_{\Gjk\in A}\gjk = O_{\epsilon,\kappa,\CC,W}(1)$, independent
of~$m$.
%
\item The groups of $B$ are all large:\\
\centerline{$\forall(\Gjk\in B), \gjk\geq \kappa |A|^2$}
%
\item The messages in $C$ have negligible contribution if they 
are scheduled rarely (with density~$O(\epsilon/\CC )$):\\
\centerline{$\LB_{W=1}(C,\frac{\epsilon}{10\CC}) 
\leq \frac{3\epsilon}{10}\OPT(M)$}
\end{enumerate}
\end{lemma}

\begin{proofSketch} 
Since the proof is rather technical, we will only in this extended
abstract give the construction of the partition into $A,B$ and $C$ in
the case when there are no costs ($\CC =0$) and there is only one
broadcast channel ($W=1$); this already contains the gist of the
proof.

Let $a=(1+\epsilon)^{-1}<1$.
In the case where there are no costs, the lower bound can be solved
explicitly (see \cite{AW85,BBNS98}) even when there is a density
constraint, to yield, for any subset $X$ of the message set:\\
\centerline{ $
\begin{array}{r@~c@~l}
LB(X,\alpha)&=
%&\frac1{2\alpha} \bigl(\sum_{M_i\in X} \sqrt{p_i}\bigr)^2
%\smallskip \\
%&=
&\frac r{2\alpha } \bigl(\sum_{G_{j}\in X} g_{j} a^{j/2}\bigr)^2
\end{array}
$}

\paragraph*{\normalfont\itshape The construction} The construction
is best understood by referring to figure~\ref{fig:partition}.  We first 
deal with indices such that~$g_{j} \leq a^{-j/4}$. Let $j_0$ be some
constant to be defined later, and define $C_1 = \{ (j: j > j_0,~
g_{j} \leq a^{-j/4}\}$, and $A_1 = \{ j : j \leq j_0,~ g_{j}
\leq a^{-j/4}\}$. (One can observe already that since the contributions
of the messages of $C_1$ form the tail of a geometrically decreasing
series, they will be negligible, and so they will end up in $C$; moreover,
since $j$ and $g_j$ are both bounded for the definition of $A_1$, set
$A_1$ can only contain a small number of messages and so these messages
will end up in $A$).

We now consider the more delicate case of the
groups for which $g_{j} >a^{-j/4}$, for which we will need to use
the pigeon hole principle. We
partition their indices into $(20/\epsilon)$~blocks as
follows:
%
$$
\begin{array}{r@~c@~l}
\Lambda_1 & = & \{ (j,k) : \mu \leq j < \mu^2 \},
\smallskip \\
\Lambda_2 & = & \{ (j,k) : \mu^2 \leq j < \mu^3  \}, \ldots
\smallskip \\
\Lambda_{20/\epsilon} & = &  
\{ (j,k) : \mu^{20/\epsilon} \leq j
< \mu^{1+20/\epsilon} \},
\end{array}
$$
%
where $\mu$~is some constant to be defined later.  According
to~\cite{AW85}, we can then rewrite the lower bound on the expected
response time as $\sqrt{2 LB(M)/r} = \sum_j g_{j} a^{j/2}
\geq \sum_h \sum_{j\in\Lambda_h} g_{j} a^{j/2}$, and the pigeon
hole principle tells us that there exists at least one~$h$ such that
$\sum_{j\in \Lambda_h} g_j a^{j/2} \leq \frac{\epsilon}{20}
\sqrt{2 LB(M)/r}$. We now define $A_2 =
\{ j:j < \mu ^h,~ g_{j}>a^{-j/4} \}$, $C_2 = \Lambda_h$, and
$B = \{ j:j > \mu ^h,~ g_{j}>a^{-j/4} \}$.
%The previous definition of A_2 was wrong: we want A_2 to also
%contain indices before Lambda_1 !

Finally we set $A = A_1 \cup A_2$ and $C = C_1 \cup C_2$
 as shown on Figure~\ref{fig:partition}.

\begin{figure}[htb]
\inputfig{partition}
\caption{The partition.} \label{fig:partition}
\end{figure}
\end{proofSketch}

%\subsection{A PTRAS for the Data Broadcast problem}
It is now a simple matter to take our building blocks
and deduce a randomized approximation scheme for the general
Data Broadcast problem.

\begin{proposition}[PTRAS] \label{pro:PTRAS}
Given~$0<\epsilon<1/7$, the randomized algorithm~\ref{algo:PTRAS}
yields a random schedule~$S$ with cost: $$
\expect[\COST(S)] \leq (1+10\epsilon)\OPT(M)
$$
\end{proposition}

\begin{algorithm}[htb]
\caption{A PTRAS} \label{algo:PTRAS}
\begin{algorithmic}
\STATE $\CD$ Round the probabilities and costs of the messages in~$M$,
        and partition the set of messages~$M$ into three sets~$A,B,C$,
        according to Lemma~\ref{lem:partition} with
        $\kappa=\kappa(\epsilon)$.
\STATE $\CD$ Schedule $A$ and $B$ with algorithm~\ref{algo:A+B}.
\STATE $\CD$ Insert the messages of~$C$ into the schedule of~$A$ and~$B$, 
with the algorithm described in Lemma~\ref{lem:scheduleC}.
\end{algorithmic}
\end{algorithm}

\begin{proof}
Consider the rounded instance~$\dM$ of the set of messages. According
to the previous Proposition~\ref{pro:A+B} and
Lemma~\ref{lem:scheduleC}, we have:\\
\centerline{$
\expect[\COST(S)] \leq (1+\epsilon)(1+5\epsilon)\OPT(\dM)
$} But Lemma~\ref{lem:rounding} ensures that: \\
\centerline{$
\OPT(\dM)\leq(1+3\epsilon)\OPT(M)$}
which yields the result.
\end{proof}

\begin{note}
The insertion of~$C$ can be done at the same time than the broadcast
of~$A$ and~$B$ in Algorithm~\ref{algo:PTRAS}. 
\end{note}

\subsection{Derandomization}
\label{sec:derando}

The PTRAS has one slight problem, namely, that it is not periodic,
hence may be somewhat awkward to implement in some settings. In this
section we derandomize it using greedy choices, and show how
to control the period of the resulting algorithm.
\begin{definition}[State] \label{not:greedystate}
%At slot $t$, we number the $g_j$ last broadcasts of each group $G_j$
%from $1$ to $g_j$ from the left to the right. 
We define the \emph{state} $(s^t_{j,k})_{1\leq j\leq q, 1\leq k\leq
g_j}$ at slot $t$ as the time period elapsed from the beginning of
the $k\th$ of the $g_j$ last broadcasts of group $G_j$ to the end of
slot $t$, as shown Figure~\ref{fig:greedystate}.
\end{definition}

\begin{figure}[htb]
\inputfig{st_jk}
\caption{Definition of the state at time slot $t$.}
\label{fig:greedystate}
\end{figure}

\begin{lemma}[Derandomization of Algorithm~\ref{algo:rando}] \label{lem:greedy}
Given a set of messages partitioned into groups $\series G1q,$ of
size $g_j$, and a set of reals $\tau_j>0$ so that $\sum_j 1/\tau_j \leq
1$, the greedy algorithm~\ref{algo:greedy} yields a one-channel
schedule $S$ whose cost satisfies:$$
\COST(S) \leq \sum_{j=1}^q \left(
        p_j \frac{g_j(g_j+1)}2 \tau_j + \frac{c_j}{\tau_j}
        \right) -\frac12
$$
%
If $\tau$~minimizes~$\LB(M,1)$, we get a $\max_j(1+1/g_j)$-approximation.
\end{lemma}

\begin{algorithm}[htb]
\caption{Greedy Algorithm}\label{algo:greedy}
\begin{algorithmic}
%\REQUIRE \textsl{
%       A set of groups $\series G1q,$ where the messages of $G_j$ are
%       requested with probability~$p_j$ and have a broadcast
%       cost~$c_i$. We denote by $g_j = |G_j|$; we have $\sum_{j=1}^q
%       g_j p_j = 1$.\\ We are also given the $\tau_j\geq1$ so that
%       $\sum_{j=1}^q 1/\tau_j \leq 1$.}
%\\[.1em]
%\IF{$\sum_{j=1}^q 1/\tau_j < 1$}
\STATE $\CD$ Add a dummy group $G_0$, if needed.
% with $g_0=p_0=c_0=0$ and
%       $\tau_0$ so that $1/\tau_0 = 1-\sum_{j=1}^q 1/\tau_j$.
%\ENDIF
%\ENSURE
\FOR{$t=1..\infty$}
        \STATE $\CD$ Let $(s_{j,k})$ be the state at time slot $t-1$.
% as defined Figure~\ref{fig:greedystate}/Notation~\ref{not:greedystate}.  
        \STATE $\CD$ Let $j\in\{0,\ldots,q\}$ which minimizes:\\
        \centerline{$(c_j-p_j\tau_j\sum_{k=1}^{g_j} s_{j,k})$}
        \STATE $\CD$ Schedule during slot $t$, the next message of $G_j$ in
        the Round Robin order, if $j\neq0$, and stay idle otherwise.
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{proofSketch}
The greedy choice at time slot~$t$ is made in order to minimize the
expected cost of the already allocated slots~$1,\ldots,(t-1)$, if the
schedule continues with the randomized algorithm~\ref{algo:rando}
after time~$t$; this property ensures that the greedy schedule is at
least as good as the randomized one.
\end{proofSketch}

The above greedy algorithm could conceivably have very large period.
The lemma below shows that we can truncate it so as to obtain
a periodic schedule of polynomial length.
\begin{corollary}[Greedy periodic schedule] \label{lem:periodicgreedy}
Given a set of messages partitioned into groups $\series G1q,$ of
size $g_j$,  a set of reals $\tau_j>0$ such that $\sum_j 1/\tau_j
\leq W$, and any~$T \geq (8m^2+(4\CC-1)m)$, 
Algorithm~\ref{algo:periodicgreedy} yields a one-channel schedule~$S$
with period~$(T+2m)$, whose cost is bounded by: $$
\COST(S) \leq \sum_{j=1}^q \left(
        p_j \frac{g_j(g_j+1)}2 \tau_j + \frac{c_j}{\tau_j}
        \right)
$$
\end{corollary}

\begin{algorithm}[htb]
\caption{A periodic greedy algorithm} \label{algo:periodicgreedy}
\begin{algorithmic}
\STATE $\CD$ Schedule during slot $t=1..m$ message $M_t$.
\STATE $\CD$ Execute the greedy algorithm during slots $t=(m+1)..(T+m)$.
\STATE $\CD$ Sort in increasing order the set $\{k\tau_j: 1\leq j\leq q; 
1\leq k\leq g_j\}$ and Schedule in slots $t=(T+m+1)..(T+2m)$ in order
of increasing $k\tau_j$, the $k\th$ message of group $G_j$ in the
Round Robin order.
\end{algorithmic}
\end{algorithm}

\begin{proof}
Omitted.
\end{proof}

Our main algorithm can now be found in Algorithm~\ref{algo:PTAS}.
\begin{algorithm}[htb]
\caption{The PTAS} \label{algo:PTAS}
\begin{algorithmic}[1]
\STATE  Round the probabilities and costs, and 
partition~$M$ into~$A,B,C$ as in the PTRAS.
\STATE Compute $\tau^*$ and the density $\alpha_0$ and periodic
schedule $S_{\alpha_0}$ of $A$ to minimizes $\LB(B,(1-\alpha_0)$, as in Algorithm 2.
\STATE Compute the greedy periodic schedule~$S_B$ of~$B$ 
with $\tau=(\tau^*(1-\alpha_0)W)$ and with
period~$\bigl\{T(\epsilon)|A|^2(1-\alpha_0)W(8m^2+(4\CC +1)m)\bigr\} =
\Theta(m^2)$.
\STATE Concatenate $(8m^2+(4\CC+1)m)$ periods of~$S_{\alpha_0}$ and 
map~$S_B$ into the empty slots in the natural order.
\STATE Compute the greedy periodic schedule~$S_C$ of~$C$ 
with $\tau=(10\CC\tau^*/\epsilon)$ where $\tau^*$~minimizes
$\LB(C,\epsilon/10\CC)$, and with period~$\bigl\{T(\epsilon)|A|^2(8m^2+(4\CC
+1)m)\epsilon/10\CC\bigr\} = \Theta(m^2)$.
\STATE Choose the best starting point in~$\{1,\ldots,\frac{10\CC}\epsilon-1\}$
and stretch the schedule of $A$ and $B$ by inserting a slot of~$S_C$
on the first channel every $(\frac{10\CC}\epsilon-1)$ and an empty slot
on the other channels at that time. Let $S$ be the
resulting schedule.
\STATE Choose the best starting point 
in~$\{1,\ldots,\frac{m^2+m\CC}\epsilon-m\}$ and construct~$S'$ by
stretching~$S$ by inserting the $m$~messages in fixed order on the
first channel every $(\frac{m^2+m\CC}\epsilon-m)$.
\STATE $S'$ is then structured into independent blocks of
length $\frac{m^2+m\CC}\epsilon$. The cheapest block~$S^*$ will be the
period of our approximation.
\end{algorithmic}
\end{algorithm}

\begin{proofOf}{Theorem~\ref{thm:PTAS}}
Theorem~\ref{thm:PTAS} is proved by analyzing the
algorithm~\ref{algo:PTAS}. The analysis is derived from the analysis
of the PTRAS. The six first steps are exactly the same, except that
the periodic greedy algorithm~\ref{algo:periodicgreedy} is used
instead of the randomized algorithm~\ref{algo:rando}. Since the
performance ratio in Algorithm~\ref{algo:periodicgreedy} is better,
the schedule~$S$ obtained Step~6 is at least as good, and is periodic
with period~$O(m^2)$: \\
\centerline{$
\COST(S) \leq (1+10\epsilon)\OPT(M)
$}

We finally reduce the period in Steps~7-8 by using  stretching
lemma~\ref{lem:stretching}, which ensures that at an increase of
$(1+O(\epsilon))$ of the cost, we can extract from~$S$ a block~$S^*$
with length $\leq\frac{m^2+m\max(1,\CC)}\epsilon$ and:\\
\centerline{$
\COST(S^*) \leq (1+11\epsilon)\OPT(M)
$}
\end{proofOf}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% T E C H N I C A L   L E M M A S
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Technical lemmas}\label{sec:technical}

The lemmas in this sections are useful for analyzing several of
our constructions. The stretching lemma states that changing a schedule
by inserting a few empty slots once in a while does not affect
the expected response time.
%\subsection{Stretching}

\begin{lemma}[Stretching] \label{lem:stretching}
Given a schedule~$S$ on $W$~channels of~$M$ and a positive
integer~$y$, let $\kappa \geq \frac{y^2+y}\epsilon-y$. Consider the
schedule~$S'$ obtained from~$S$ by inserting~$y$ empty slots just
before the time slots~$x,x+\kappa,\ldots,x+i\cdot\kappa,\ldots$, where
$x$~is a random time in~$\{1,\ldots,\kappa\}$. Then: $$
\expect[\ART(S')] \leq (1+\epsilon)\ART(S)
$$
\end{lemma}

\begin{proof}
Omitted.
\end{proof}

%\subsection{Scheduling in reserved empty slots}
The scaling lemma is immediate.
\begin{lemma}[Scaling] \label{lem:scaling}
Given a set of messages $M$ and a schedule $S$, let $S_\alpha$ the
schedule obtained by scaling $S$ by a factor $1/\alpha$: $S_\alpha$
schedule at time $t/\alpha$ on some channel the same message as $S$ at
time $t$, and stays idle otherwise. Then:
\begin{eqnarray*}
\ART(S_\alpha,A) & = & \cfrac1\alpha\cdot\ART(S,A) \\
\BC(S_\alpha,A) & = &  \alpha \cdot \BC(S,A)
\end{eqnarray*}
\end{lemma}

\begin{proof}
Immediate.
\end{proof}

%\begin{remark}
%This will be used to schedule $C$ every 
%\end{remark}

The mapping lemma is used for analyzing the effect of inserting
the messages from $B$ into the slots left empty in the 
density-constrained schedule of $A$; these slots may be spaced
irregularly.
\begin{lemma}[Mapping into reserved empty slots] \label{lem:mapping}
Given a set of messages~$M$, partitioned into groups of 
identical messages, such that all groups are larger than $TW$,
consider a one-channel schedule $S$ of $M$ scheduling each group in
Round Robin order, and a periodic sequence of reserved time-slots over
$W$~channels with density~$\alpha$ and period~$T$. Let~$S'$ be
the schedule obtained by mapping the schedule~$S$ into the reserved
empty slots from left to the right, then:
\begin{eqnarray*}
\ART(S',A) & \leq & \cfrac1{\alpha W} \cdot \ART(S,A) 
                        + T \sum_{M_i\in A} p_i \\
\BC(S',A) & = &  \alpha W \cdot\BC(S,A)
\end{eqnarray*}
\end{lemma}

\begin{proof}
Omitted.
\end{proof}

\begin{corollary}[Case of large groups]
In the case where $M$~is partitioned into  groups of size~$\geq
2T/\epsilon$, $S'$~has a cost bounded by: \smallskip \\
$~~~\COST(S',A) \leq$\\
$~~~~~~~~~~~~~~(1+\epsilon) \biggl\{ \cfrac1{\alpha W}\cdot 
\ART(S,A) + \alpha W \cdot \BC(S,A) \biggr\} $
\end{corollary}

\begin{proof}
Simple calculation.
\end{proof}

\begin{thebibliography}{10}

\bibitem{A98}
{\sc Acharya, S.}
\newblock {\em Broadcast Disks: Dissemination-based Management for Asymmetric
  Communication Environments}.
\newblock PhD thesis, Brown University, 1998.

\bibitem{A87}
{\sc Ammar, M.~H.}
\newblock Response time in a Teletext system: An individual user's perspective.
\newblock {\em IEEE Transactions on Communications COM-35,11\/} (Nov. 1987),
  1159--1170.

\bibitem{AW85}
{\sc Ammar, M.~H., and Wong, J.~W.}
\newblock The design of Teletext broadcast cycles.
\newblock In {\em Performance Evaluation\/} (1985), vol.~5(4), pp.~235--242.

\bibitem{AW87}
{\sc Ammar, M.~H., and Wong, J.~W.}
\newblock On the optimality of cyclic transmission in Teletext systems.
\newblock In {\em IEEE Trans. on Comm.\/} (1987), vol.~COM-35(11),
  pp.~1159--1170.

\bibitem{AGH98}
{\sc Anily, S., Glass, C.~A., and Hassin, R.}
\newblock The scheduling of maintenance service.
\newblock To appear (\textsf{http://www.math.tau.ac.il/$\sim$hassin}).

\bibitem{BBNS98}
{\sc Bar-Noy, A., Bhatia, R., Naor, J.~S., and Schieber, B.}
\newblock Minimizing service and operation costs of periodic scheduling.
\newblock In {\em Proc. of the 9th Annual ACM-SIAM Symp. on Discrete Algorithms
  (SODA)\/} (1998), pp.~11--20.

\bibitem{BC96}
{\sc Bestavros, A., and Cunha, C.}
\newblock Server-Initiated Document Dissemination for the WWW.
\newblock {\em IEEE Data Engineering Bulletin}, September 1996.

\bibitem{BS99}
{\sc Bar-Noy, A., and Shilo, Y.}
\newblock Optimal broadcasting of two files over an asymmetric channel.
\newblock In {\em Proc. of Infocom\/} (1999).

\bibitem{CC93}
{\sc Chan, M.~Y., and Chin, F.}
\newblock Schedulers for larger classes of pinwheel instances.
\newblock {\em Algorithmica 9\/} (Jun. 1993), 425--462.

\bibitem{G83}
{\sc Gecsei, J.}
\newblock The architecture of videotex systems.
\newblock {\em Prentice Hall, Englewood Cliffs, N.J.\/} (1983).

\bibitem{HW63}
{\sc Hadley, G., and Whitin, T.~M.}
\newblock {\em Analysis of inventory systems}.
\newblock Prentice-Hall, 1963.

\bibitem{HR87}
{\sc Hofri, M., and Rosberg, Z.}
\newblock Packet delay under the golden ratio weighted {TDM} policy in a
  multiple-access channel.
\newblock In {\em IEEE Trans. on Information Theory\/} (May 1987), vol.~11(33),
  pp.~341--349.

\bibitem{HMRTV89}
{\sc Holte, R., Mok, A., Rosier, L., Tulchinsky, I., and Varvel, D.}
\newblock The pinwheel: A real-time scheduling problem.
\newblock In {\em Proc. 22nd Hawaii Int. Conf. Syst. Sci.\/} (Jan. 1989),
  pp.~693--702.

\bibitem{IVB94}
{\sc Imielinski, T., Viswanathan, S., and Badrinath, B.}
\newblock Energy efficient indexing on air.
\newblock In {\em SIGMOD\/} (May 1994).

\bibitem{IR84}
{\sc Itai, A., and Rosberg, S.}
\newblock A golden ratio control policy for a multiple-access channel.
\newblock {\em IEEE Transactions on Autom. Contr. AC-29\/} (Aug. 1984).

\bibitem{KS99}
{\sc Kenyon, C., and Schabanel, N.}
\newblock The data broadcast problem with non-uniform transmission times.
\newblock In {\em Proc. of the 10th SODA\/} (1999), pp.~547--556.

\bibitem{KL98}
{\sc Khanna, S., and Liberatore, V.}
\newblock On broadcast disk paging.
\newblock In {\em Proceedings of 30th STOC\/} (1998), vol.~30, pp.~634--643.

\bibitem{KZ98}
{\sc Khanna, S., and Zhou, S.}
\newblock On indexed data broadcast.
\newblock In {\em Proceedings of 30th STOC\/} (1998), vol.~30, pp.~463--472.

\bibitem{S00}
{\sc Schabanel, N.}
\newblock The data broadcast problem with preemption.
\newblock In {\em LNCS Proc. of the 17th Symp. on Theor. Aspects of 
Comp. Sc. (STACS 2000)} (Feb. 2000, to be published).

\bibitem{SL96}
{\sc Shekhar, S., and Liu, D.}
\newblock Genesis: An approach to data dissemination in {A}dvanced {T}raveller
  {I}nformation {S}ystems ({ATIS}).
\newblock In {\em IEEE Data Engineering Bulletin\/} (Sept. 1996), vol.~19(3).

\bibitem{ST97}
{\sc Su, C.-J., and Tassiulas, L.}
\newblock Broadcast scheduling for information distribution.
\newblock In {\em Proc. of INFOCOM\/} (1997).

\bibitem{TX96}
{\sc Tan, K., and Xu, J.}
\newblock Energy efficient filtering of nonuniform broadcast.
\newblock In {\em Proc. of the 16\th~Int. Conf. in Distributed Computing
  System\/} (1996), pp.~520--527.

\bibitem{VH97}
{\sc Vaidya, N., and Hameed, S.}
\newblock Log time algorithms for scheduling single and multiple channel data
  broadcast.
\newblock In {\em Proc. of the 3rd ACM/IEEE Conf. on Mobile Computing and
  Networking (MOBICOM)\/} (Sep. 1997).

\bibitem{V94}
{\sc Vishwanath, S.}
\newblock {\em Publishing in wireless and wireline environments}.
\newblock PhD thesis, Rutgers University, 1994.


\end{thebibliography}

\end{document}


\appendix

\section{Omitted proofs}

\subsection{Bounding the period of~$A$}

\begin{proofOf}{Lemma~\ref{lem:boundedperiod}}
First, remark that we can restrict to the case
where~$\alpha\leq(1-\epsilon/5)$, by losing a factor
of~$(1+\epsilon/5)$ to the cost: If $\alpha\geq (1-\epsilon/5)$,
consider an optimal schedule~$S$ with density~$\alpha$, with
cost~$\OPT(A,\alpha)$, and construct~$S'$ from~$S$ by inserting every
$(5/\epsilon-1)$~slots an empty time slot on all the channels,
starting at a random point. The stretching lemma~\ref{lem:stretching}
ensures that, for some starting point:\\
\centerline{$
\COST(S')\leq(1+\epsilon/5)\OPT(A,\alpha)
$} 
%
And the density of~$S'$ is exactly: $(1-\epsilon/5)\alpha$
($\leq(1-\epsilon/5)$). Note that this makes the first condition
easier.

Consider $S^*$ a nearly optimal periodic schedule of~$A$ with
density~$\alpha$, such that:\\
\centerline{$
\COST(S^*)\leq\frac{1+2\epsilon/3}{(1+\epsilon/3)(1+\epsilon/4)}
\OPT(A,\alpha)$}
%
Let $T^*$ denote the period of~$S$.

Assume that $\CC\geq1$ and let $T=\cfrac{6
|A|^2\CC}{\epsilon}-|A|$. By multiplying the period~$T^*$ by~$T$, we
can assume {\WLOG}, that: $T^*$ is a multiple of~$T$.

We construct~$S_1$ by inserting in~$S^*$, every $T$~slots, a series
of~$|A|$ empty slots on all the channels, starting at the point
in~$\{0,\ldots,T-1\}$, that minimizes the over cost. The stretching
lemma~\ref{lem:stretching} ensures that:\\
\centerline{$
\COST(S_1) \leq (1+\epsilon/3) \COST(S^*)$}
%
Furthermore, the density~$\alpha_1$ of~$S_1$ satisfies:\\
\centerline{$
\alpha_1=\alpha\bigl(1-\frac{\epsilon}{6|A|\CC}\bigr)$}
%
We construct~$S_2$ from~$S_1$ by inserting within all the new empty
slots the $|A|$~messages of~$A$ in fixed order; the expected response
time decreases and the broadcast over cost is bounded by~$\epsilon/6$:\\
\centerline{$
\COST(S_2)\leq \COST(S_1)+\epsilon/6$}
%
Moreover, the density~$\alpha_2$ of~$S_2$ satisfies:\\
\centerline{$
(1-\alpha_2)\geq(1-\epsilon/6)(1-\alpha)$}

$S_2$ is then structured into independent \emph{blocks}, of
length~$T+|A|$, defined as the parts of~$S_2$ beginning at the end of
the series of inserted slots and ending at the end of the next
series. We define the \emph{cost} of a block as the sum of the expected
response time to the requests that are served in this block, and of
the average broadcast cost of the messages broadcast in this
blocks. Since all the block end with all the messages of~$A$ in fixed
order, one can see that the cost (resp. density) of~$S_2$ is the
uniform average cost (resp. density) of the blocks; in particular,
permuting them do not change the cost (and density) of~$S_2$, and
furthermore the expected cost (resp. density) of a block
is~$\COST(S_2)$ (resp.~$\alpha_2$). We show next that we can sample a
constant number of the blocks, and concatenate them into a periodic
schedule, with almost the same density and almost the same cost
than~$S_2$.

Let $n=\cfrac{20\ln(1+4/\epsilon)} {3 \epsilon^3(1-\epsilon/6)}$. We
construct $S_n$ by concatenating $n$~blocks, drawn independently at
random among the blocks of~$S_2$. The expected cost of a block is
$\COST(S_2)$. Then Markov inequality yields:\\
\centerline{$
\Pr\bigl\{\COST(S_n)\geq(1+\epsilon/4)\COST(S_2)\bigr\}\leq
\frac1{1+\epsilon/4}$}
%
The expected density of empty slots of a block is~$1-\alpha_2$. Then
since it is bounded in~$]0,1]$, the Chernoff bound yields: \\
\centerline{$
\begin{array}{r}
\Pr\bigl\{(1-\alpha(S_n))\leq(1-5\epsilon/6) (1-\alpha_2)\bigr\} 
\leq \qquad\qquad~\\
e^{\DS{-(5\epsilon/6)^2 n (1-\alpha_2)/2}}
\end{array}$}
%
Thus, by construction of~$n$:\\
\centerline{$
\begin{array}{l}
\Pr\Bigl\{\bigl[\COST(S_n)\geq(1+\epsilon/4)\COST(S_2)\bigr]\\
~~~~~~~\vee\bigl[(1-\alpha(S_n))\leq(1-5\epsilon/6)
(1-\alpha_2)\bigr]\Bigr\}\\
~~~~~~~~~~~~~~~~~~~~~
< \cfrac1{1+\epsilon/4} + e^{\DS{-3\epsilon^2 n (1-\alpha_2)/4}} 
< 1
\end{array}$}
%
--- we use that: $(1-\alpha_2) \geq (1-\epsilon/6)(1-\alpha) \geq
(1-\epsilon/6)\epsilon/5$.

Then, there exists a draw for which $S_n$~has cost:\\
\centerline{$
\begin{array}{r@~c@~l}
\COST(S_n)
& \leq & 
(1+\frac{2\epsilon}3)(1+\frac\epsilon5)\OPT(A,\alpha)
+(1+\frac\epsilon4)\frac\epsilon6\\
& \leq & (1+\epsilon)\OPT(A,\alpha)+\epsilon/2 \smallskip\\
(1-\alpha(S_n)) 
& \geq & (1-\frac{5\epsilon}6)(1-\frac\epsilon6)(1-\alpha) \\
& \geq & (1-\epsilon)(1-\alpha)
\end{array}$}
%
Since the density of each block is positive, $\alpha(S_n)\in]0,1[$.
Finally, the period of~$S_n$ is bounded by $n(T+|A|)$, which yields to
the result.
\end{proofOf}

\subsection{Scheduling $A$ and $B$}

\begin{proofOf}{Proposition~\ref{pro:A+B}}
The proof works in two steps:
\begin{enumerate}
\item   \label{pf:stepANA} Scheduling the messages of~$B$ with the 
randomized algorithm~\ref{algo:rando} in the empty slots achieves a
good approximation of $\COST(S_{\alpha_0},A)+\LB(B,1-\alpha_0)$ (using
the mapping lemma~\ref{lem:mapping}).
%
\item   \label{pf:stepOPT} $\COST(S_{\alpha_0},A)+\LB(B,1-\alpha_0)$ 
is a good approximation of the optimal cost (using
Lemma~\ref{lem:boundedperiod}).
\end{enumerate}
\textit{Step~\ref{pf:stepANA}.} Let~$S_{AB}$ be the random schedule 
generated by Algorithm~\ref{algo:A+B}. The contribution of the message
of~$A$ to the cost of~$S_{AB}$ is~$\COST(S_{\alpha_0},A)$. Consider
the one-channel schedule~$S_B$ of the messages of~$B$, generated by
the randomized algorithm~\ref{algo:rando} with $\tau=(\tau^*
\alpha_0W)$. Schedule~$S_{AB}$ is obtained by mapping the schedule~$S_B$
into the empty slots of~$S_{\alpha_0}$ from the left to the
right. Since all the groups in~$B$ are larger than
$2WT(\epsilon)|A|^2/\epsilon$ and $S_{\alpha_0}$ has period~$\leq
T(\epsilon)|A|^2$, Lemma~\ref{lem:mapping} proves that:\\
\centerline{$
\begin{array}{r@~c@{}l}
\expect[\COST(S_{AB},B)]
&\leq (1+\epsilon) \bigl\{ & 
\frac1{\alpha_0W}\expect[\ART(S_B,B)] \\
& & + \alpha_0W\expect[\BC(S_B,B)] \bigr\}
\end{array}$}
%
But according to Lemma~\ref{lem:rando}:\\
\centerline{$
\begin{array}{l}
\expect[\ART(S_B,B)]  \leq 
\DS\max_{k\in B}(1+2/g_k) \DS\sum_{j\in B} p_j g_j^2\tau^*_j\alpha_0W\\
\text{and, }
\expect[\BC(S_B,B)]  \leq  \sum_{j\in B} c_j/(\tau^*_j \alpha_0W)
\end{array}$}
%
Thus:\\
\centerline{$
\begin{array}{r@~c@~l}
\expect[\COST(S_{AB})] 
& \leq & (1+\epsilon)(1+2/\kappa(\epsilon)) \LB(B,1-\alpha_0)\\
& \leq & (1+2\epsilon)\LB(B,1-\alpha_0)
\end{array}$} 
%
Finally: \\
\centerline{$
\begin{array}{l}
\expect[\COST(S_{AB})] \leq\\
~~~~~~~~~~(1+2\epsilon)\bigl\{\COST(S_{\alpha_0},B)+\LB(B,1-\alpha_0)\bigr\}
\end{array}
$}

\textit{Step~\ref{pf:stepOPT}.} Consider an optimal schedule~$S^*$
of~$A\cup B$, and let~$\alpha^*$ be the density of~$A$ in~$S^*$:\\
\centerline{$
\begin{array}{r@~c@~l}
\OPT(A\cup B) 
& = & \COST(S^*) \\
& \geq & \OPT(A,\alpha^*)+\LB(B,1-\alpha^*)
\end{array}$}
Lemma~\ref{lem:boundedperiod} ensures that there exists a schedule~$S$
with period~$\leq T(\epsilon)|A|^2$, with density~$\alpha\in]0,1[$ so
that: \\
\centerline{$
\begin{array}{l}
(1-\alpha)\geq(1-\epsilon)(1-\alpha^*)\\
\text{and, } \COST(S,A)\leq (1+\epsilon)\OPT(A,\alpha^*)+\epsilon/2
\end{array}$}
%
By construction of~$\alpha_0$:\\
\centerline{$
\begin{array}{l}
\COST(S_{\alpha_0},A)+\LB(B,1-\alpha_0) \\
~~~~~~~~~~~~~~~~~~~~~~\leq \COST(S,A)+\LB(B,1-\alpha)
\end{array}$}

Consider the solution~$\tau^*$ to the minimization
problem~$\LB(B,1-\alpha^*)$, and let $\tau=\tau^*/(1-\epsilon)$. We
have:\\
\centerline{$
\sum_{j\in B} 1/\tau_j \leq (1-\epsilon)(1-\alpha^*)W\leq(1-\alpha)W$}
%
Thus $\tau$~is a realizable point of the minimization
problem~$\LB(B,1-\alpha)$, and:\\
\centerline{$
\begin{array}{r@~c@~l}
\LB(B,1-\alpha)
& \leq & \sum_j (p_j g_j^2 \tau_j + c_j/\tau_j) \\
& \leq & \frac1{1-\epsilon}\sum_j (p_j g_j^2 \tau^*_j + c_j/\tau^*_j) \\
& \leq & \LB(B,1-\alpha^*)/(1-\epsilon)
\end{array}$}

Finally: 
$$
\begin{array}{l}
\COST(S_{\alpha_0},A)+\LB(B,1-\alpha_0)\\
~~~~\leq (1+\epsilon) \OPT(A,\alpha^*)+\frac\epsilon2
+\frac1{1-\epsilon}\LB(B,1-\alpha^*)\\
~~~~\leq \OPT(A\cup B)/(1-\epsilon)+\epsilon\OPT(A\cup B)\\
~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{since, $\OPT(A\cup B)\geq 1/2$}\\
~~~~\leq \frac{1+\epsilon}{1-\epsilon}\OPT(A\cup B)
\end{array}$$
%
We conclude that:
$$
\begin{array}{l}
\expect[\COST(S_{AB})]\\
~~~~~~~~~~~\leq \cfrac{(1+2\epsilon)(1+\epsilon)}{1-\epsilon}\OPT(A\cup B)\\
~~~~~~~~~~~\leq (1+5\epsilon)\OPT(A\cup B) \text{, since $\epsilon<1/7$}
\end{array}$$
\end{proofOf}

\subsection{Partition}

\begin{proofOf}{Lemma~\ref{lem:rounding}}
Round each message probability~$p_i$ to $\dP_i=r/(1+\epsilon)^j$, with
$1< r\leq (1+\epsilon)$, and each message cost~$c_i$ down to
$\dC_i = k\epsilon/W$, with $k\epsilon/W\leq c_i < (k+1)\epsilon/W$. This creates a new instance~$\dM$ in which: $$
\dP_i \leq r p_i < (1+\epsilon) \dP_i \text{, and }
\dC_i \leq c_i < \dC_i +\epsilon/W
$$ 
%
Now, if for any schedule~$S$ of~$M$, $\dS$~denotes the corresponding
schedule of~$\dM$, consider $S_1$, an optimal schedule of~$M$ and
$S_2$, an optimal schedule of~$\dM$. Consider the corresponding
schedule~$S_2$ of the optimal rounded schedule~$\dS_2$, we have: $$
\begin{array}{r@~c@~l}
r \COST(S_2) 
& \leq & (1+\epsilon) \ART(\dS_2) + r (\BC(\dS_2) + \epsilon)\\
& \leq & (1+\epsilon) \COST(\dS_2) + r\epsilon\\
& \leq & (1+\epsilon) \COST(\dS_1) + r\epsilon\\
& \leq & (1+\epsilon) (r \ART(S_1) + \BC(S_1)) + r\epsilon\\
& \leq & (1+\epsilon) r \COST(S_1) + r \epsilon 
\smallskip\\
\COST(S_2) & \leq & (1+3\epsilon) \OPT(M) \text{, since $\OPT\geq\frac12$}
\end{array}
$$
\end{proofOf}

\begin{proofOf}{Lemma~\ref{lem:partition}}
Let $a=(1+\epsilon)^{-1}<1$.

In order to bound the contribution of~$C$, we introduce
$\LBNoC(X,\alpha)$ the lower bound on the contribution to the cost of
a subset~$X\subseteq M$ with density~$\alpha\in]0,1]$, if the broadcast
costs are zero. We have: \smallskip\\
\centerline{$
\LBNoC(X,\alpha)\leq\LB(X,\alpha)\leq\LBNoC(X,\alpha)+\alpha\CC W
$} \smallskip

Furthermore, $\LBNoC(X)$ can be solved explicitly
(see \cite{AW85,BBNS98}):\\
\centerline{ $
\begin{array}{r@~c@~l}
\LBNoC(X,\alpha)&=&\frac1{2\alpha W} \bigl(\sum_{M_i\in X} \sqrt{p_i}\bigr)^2
\smallskip \\
&=&\frac r{2\alpha W} \bigl(\sum_{G_{j,k}\in X} g_{j,k} a^{j/2}\bigr)^2
\end{array}
$}

\paragraph*{\normalfont\itshape The construction} We first 
deal with indices such that~$g_{j,k} \leq a^{-j/4}$. Let $j_0$ be some
constant to be defined later, and define $C_1 = \{ (j,k): j > j_0,~
g_{j,k} \leq a^{-j/4}\}$, and $A_1 = \{ (j,k) : j \leq j_0,~ g_{j,k}
\leq a^{-j/4}\}$.

We now consider the groups for which $g_{j,k} >a^{-j/4}$, and
partition their indices into $(20\sqrt{\CC W}/\epsilon)$~blocks as
follows:
%
$$
\begin{array}{r@~c@~l}
\Lambda_1 & = & \{ (j,k) : \mu \leq j < \mu^2 \},
\smallskip \\
\Lambda_2 & = & \{ (j,k) : \mu^2 \leq j < \mu^3  \}, \ldots
\smallskip \\
\Lambda_{{20\sqrt{\CC W}}/\epsilon} & = &  
\{ (j,k) : \mu^{{20\sqrt{\CC W}}/\epsilon} \leq j
< \mu^{1+{20\sqrt{\CC W}}/\epsilon} \},
\end{array}
$$
%
where $\mu$~is some constant to be defined later.  According
to~\cite{AW85}, we can then rewrite the lower bound on the expected
response time as $\sqrt{2W\LBNoC(M)/r} = \sum_{j\geq 1,k} g_{j,k} a^{j/2}
\geq \sum_h \sum_{j\in\Lambda_h,k} g_{j,k} a^{j/2}$, and the pigeon
hole principle tells us that there exists at least one~$h$ such that
$\sum_{j\in \Lambda_h} g_j a^{j/2} \leq \frac{\epsilon}{20\sqrt{\CC W}}
\sqrt{2W \LBNoC(M)/r}$. We now define $A_2 =
\{ (j,k):j < \mu ^h,~ g_{j,k}>a^{-j/4} \}$ and $C_2 = \Lambda_h$.
%The previous definition of A_2 was wrong: we want A_2 to also
%contain indices before Lambda_1 !

Finally we set $A = A_1 \cup A_2$, $C = C_1 \cup C_2$ and $B = \mathbb
N \smallsetminus(A\cup C)$ as shown on Figure~\ref{fig:partition}.

\paragraphtitle{The analysis.}
We now need to check that all three properties are satisfied.  For
this, we will set $j_0=4 \log_{1/a}\left(\frac{20\CC^{3/2}
W(1+\epsilon)}{\epsilon^2(1-a^{1/4})}\right) = O(1)$ and $\mu = \max
\left( j_0+1, 4\log_{1/a}\left(\kappa/\epsilon^2\right)+8
\right) = O(1)$.
\begin{enumerate}
\item   Since $\sum_{j\geq1} g_j a^{j} \leq 1$, for every $j$ we have
    $g_j \leq a^{-j}$; and as $\mu^h \geq \mu > j_0$:
%
    $$
    |A| \leq \sum_{1\leq j<\mu^h; k} g_{j,k} \leq
    \frac{\CC W}\epsilon \sum_{1\leq j<\mu^h} a^{-j}
    \leq \frac{\CC W a^{-\mu^h}}{\epsilon^2}
$$
%
    Since $h\leq\frac{20\sqrt{\CC W}}\epsilon$, the size of $A$
    depends only on $\epsilon$, $\kappa$, $W$ and $\CC$, and is then
    constant.

\item   Let $(j,k)\in B$, then $g_{j,k} \geq a^{-j/4}
    \geq \beta^{-\mu^{s+1}/4}$,
    thus:
    \begin{eqnarray*}
    \frac{g_j}{|A|^2}
    & \geq & a^{-\mu^{h+1}/4} \cdot
    \frac{\epsilon^2}{a^{-2\mu^h}}\\
    & \geq & \epsilon^2 \cdot a^{2-\frac\mu4}
        ~~~\text{ since $\mu \geq 8$ and $h\geq 1$}\\
    & \geq & \kappa ~~~\text{ by definition of $\mu$.}
    \end{eqnarray*}

\item   First, note that:\\
        \centerline{$
        \LB_{W=1}(C,\frac\epsilon{10\CC}) 
        \leq \LBNoC_{,W=1}(C,\frac\epsilon{10\CC}) + \frac{\epsilon}{10}
        $} \smallskip\\
        %
        Since $\OPT(M)\geq1/2$, we need to prove that: \\
        \centerline{$
        \LBNoC_{,W=1}(C,\frac\epsilon{10\CC}) \leq \frac{\epsilon}{10} \OPT(M)
        $} \smallskip\\
        %
        By construction of~$j_0$:\\
        \centerline{$
        \begin{array}{r@~c@~l}
        \LBNoC(C_1,\frac\epsilon{10\CC}) & = &
        \frac{10\CC r}{2\epsilon} \bigl(
                \sum_{(j,k)\in C_1} g_{j,k} a^{j/2} \bigr)^2 \\
        & \leq & \frac{5\CC^3 W^2 (1+\epsilon)}{\epsilon^3} \Bigl(
                \frac{a^{j_0/4}}{1-a^{1/4}} \Bigr)^2 \\
        & \leq & \frac{\epsilon}{80}\leq \frac{\epsilon}{40}\OPT(M)
        \end{array}$}
        
        Finally, by construction of~$\Lambda_h$: \\ 
        \centerline{$
        \begin{array}{r@~c@~l}
        \LBNoC(C_2,\frac\epsilon{10\CC}) 
        & = & \frac{10\CC r}{2\epsilon} \bigl(
                \sum_{(j,k)\in \Lambda_h} g_{j,k} a^{j/2} \bigr)^2\\
        & \leq & \frac{\epsilon}{40} \frac{r}{2W} \bigl(
                \sum_{(j,k)} g_{j,k} a^{j/2} \bigr)^2 \\
        & \leq & \frac{\epsilon}{40} \LBNoC(M) \\
        & \leq & \frac{\epsilon}{40}\OPT(M)
        \end{array}$}
        
        Putting those three bounds together yields the third statement.
\end{enumerate}
\end{proofOf}

\subsection{Derandomization}

\begin{proofOf}{Lemma~\ref{lem:greedy}}
The proof is a generalization of the proof given by~\cite{BBNS98} for
their greedy algorithm.

Let $(s^t_{j,k})_{1\leq j\leq q,1\leq k\leq g_j}$ be the state at time
slot $t$ as described Figure~\ref{fig:greedystate}. Initially, all the
$s_{j,k}$ are set to zero.

We define the cost of each time slot $t$, where a message of $G_l$ is
scheduled, as follow:

$$
C(t,S) = c_l + \sum_{j=1}^q p_j \sum_{k=1}^{g_j} (s^t_{i,k}-1/2)
$$

Remark that each interval of length $\ell$ between two consecutive
broadcast of a given message is counted in exactly $\ell$ time-slots
with values $1/2,3/2,\ldots,\ell-1/2$, which sum to $\ell^2/2$. Thus:

$$
\COST(S) = \limsup_{T\rightarrow\infty} \frac1T \DS\sum_{t=1}^T C(t,S)
$$ 

It can also be seen by remarking that, if \textit{we reverse the time},
$C(t,S)$ is the average cost for responding to a request falling into
slot $t$ and waiting for the last $g_j$ broadcasts of the messages in
$G_j$.

Let $\AVG = \sum_{j=1}^q \left(p_j \frac{g_j(g_j+1)}2 \tau_j +\frac{c
_j}{\tau_j}\right)-1/2$. In order to prove the bound on the cost of the
greedy schedule $S$, we will prove that the following function
$W(t,S)$ is non-negative:
$$
W(t,S) = \AVG - C(t-1,S) + \Phi(t-1,S) - \Phi(t,S)
$$
where the potential function $\Phi(t,S)\geq0$ will be given later.

Thus, $W(t,S)\geq0$ yields:
$$
\begin{array}{r@~c@~l}
\DS\sum_{t=1}^T C(t,S) 
& \leq &  (T+1)\AVG + \Phi(0,S) - \Phi(T,S) \\
& \leq & (T+1)\AVG
\end{array}
$$
from which the result follows.

We define the potential function $\Phi(t,S)$ as the ``expected time''
a request for a given message will have to wait after slot $t$
according to the previous schedule of the messages of its group: if
the request is waiting for the $k$\th message of the group $G_j$, with
probability $s^t_{j,k}$, it will have to wait after time slot $t$, $k$
more broadcast of a message of $G_j$, which should occur after
$k\tau_j$ time slots. Thus: $$
\Phi(t,S) = \sum_{j=1}^q p_j \sum_{k=1}^{g_j} s^t_{j,k} \cdot k\tau_j
$$

Note that $P$ satisfies the potential requirements: $\Phi(0,S) = 0$ and
$\Phi(t,S)\geq 0$.

Consider time slot $t$, let $S_l$ be the schedule which is identical
to $S$ for time slots before $t$ and schedules a message of group
$G_l$ at time slot $t$. Let now compute the value of $W(t,S_l)$:

Remark that for $j\neq l$, $s^t_{j,k} = s^{t-1}_{j,k}+1$, and
$s^t_{l,g_l} = 1$, and $s^t_{l,k<g_l} = s^{t-1}_{l,k+1}+1$. Thus:
$$
\begin{array}{l}
\Phi(t-1,S_l) - \Phi(t,S_l) \\ %=
%& & \sum_{j=1}^q \sum_{k=1}^{g_j} s^{t-1}_{j,k} \cdot k\tau_j\\
%& - & \sum_{j\neq l} p_j \tau_j \left\{ \frac{g_j(g_j+1)}2 + 
%       \sum_{k=1}^{g_j} s^{t-1}_{j,k}\cdot k \right\}
%       - p_l \tau_l \left\{ \frac{g_j(g_j+1)}2 + 
%       \sum_{k=1}^{g_l} (k-1) s^{t-1}_{l,k} \right\}\\
~~~~~~~~~~~
= - \sum_{j=1}^q p_j \frac{g_j(g_j+1)}2 \tau_j 
  + p_l\tau_l \sum_{k=1}^{g_l} s^{t-1}_{l,k}
\end{array}
$$
%
Hence: 
$$
\begin{array}{r@~c@~l}
W(t,S_l) %= 
%& &    \AVG - C(t-1,S_l) + \Phi(t-1,S_l) - \Phi(t,S_l)\\
%= & &  \sum_{j=1}^q \frac{c_j}{\tau_j} - \frac12 - c_l 
%       - \sum_{j=1}^q p_j \sum_{k=1}^{g_j} \left( s^{t-1}_{j,k} -1/2\right)
%       + p_l\tau_l \sum_{k=1}^{g_l} s^{t-1}_{l,k}\\
& = &   \DS\sum_{j=1}^q \frac{c_j}{\tau_j} - c_l \\
& &     - \DS\sum_{j=1}^q p_j \DS\sum_{k=1}^{g_j} s^{t-1}_{j,k}
        + p_l\tau_l \DS\sum_{k=1}^{g_l} s^{t-1}_{l,k}\\
\end{array}
$$
%
Now remark that $\sum_{l=0}^q 1/\tau_l = 1$ and then:
$$
\sum_{l=0}^q \frac1{\tau_l} W(t,S_l) = 0
$$

Moreover remark that:
%\begin{eqnarray*}
%W(t,S_l) - W(t,S_0) 
%& = &  - c_l - \Phi(t,S_l) + \Phi(t,S_0)\\
%& = &  - c_l   
%       - \sum_{j\neq l} p_j \sum_{k=1}^{g_j} (s^{t-1}_{j,k}+1) 
%                       \cdot k\tau_j 
%       - p_l\tau_l\left\{      \frac{g_l(g_l+1)}2 
%                               +\sum_{k=1}^{g_l} (k-1) s^{t-1}_{l,k}
%                       \right\}\\
%& &    + \sum_{j\neq0} p_j \sum_{k=1}^{g_j} (s^{t-1}_{j,k}+1) 
%                       \cdot k\tau_j \\
%& = & - c_l + p_l \sum_{k=1}^{g_l} (s^{t-1}_{l,k}+1) \cdot k\tau_l 
%       - p_l\tau_l\left\{      \frac{g_l(g_l+1)}2 
%                               +\sum_{k=1}^{g_l} (k-1) s^{t-1}_{l,k}
%                       \right\}\\ 
%\end{eqnarray*}
%Hence:
$$
W(t,S_l) = W(t,S_0) - \left( c_l - p_l\tau_l\sum_{k=1}^{g_l} s^{t-1}_{l,k}
        \right)
$$

Thus choosing the to schedule the group $G_l$ that minimizes $\left(
c_l - p_l\tau_l\sum_{k=1}^{g_l} s^{t-1}_{l,k} \right)$ ensures that
$W(t,S)\geq0$ which yields to the result! 
\end{proofOf}

\begin{proofOf}{Lemma~\ref{lem:periodicgreedy}}
The proof is basically the same as in~\cite{S99}.

Let $S$~be the periodic schedule generated by
Algorithm~\ref{algo:periodicgreedy}. As above we will consider that
the request wait for the requested message broadcast back in time, the cost is the same.

The proof of the performance ratio of the greedy algorithm above shows
that, the sum of the broadcast cost and of the cumulated expected
response time of a request arriving between time~$m$ and $T+m$, is
bounded by:
%
$$ (T+1)\AVG
-\Phi(S,T+m) + \Phi(S,m) 
$$
%
Consider the requests which arrive between time~$T+m$
and~$T+2m$, and which are served before time~$T+m$. Their
cumulated expected response time is bounded by: $$
\Phi(S,T+m) = \sum_{i=j}^q p_j 
\sum_{k=1}^{g_j} s^{T+m}_{j,k} \tau_j
$$
%
We finally need to consider the requests which arrive between time~$0$
and~$T$ and time~$T+m$ to~$T+2m$, and are served after
time~$T+m$. These requests are served after at most $2m$~time.

Note that: $$
\begin{array}{r@~c@~l}
\Phi(S,m) 
& = &   \DS\sum_{j=1}^q p_j\tau_j(g_1+\cdots+g_j)\frac{g_j(g_j+1)}2\\
& \leq &  m(\AVG+1/2)
\end{array}
$$
Finally, the cost of~$S$ is bounded by:
$$
\begin{array}{r@~c@~l}
\COST(S) & \leq & \cfrac{1}{T+2m} \left\{ 
(T+1)\AVG + m(\AVG + 1/2) \right.\\
& & ~~~~~~~~~~~~\left.+ (2m)^2 + 2m\CC \right\}
\smallskip \\
%
& \leq & \AVG + \cfrac{4m^2+(2\CC+1/2)m}{T+2m}
\end{array}
$$ 
%
which is less than~$\sum_j \bigl(p_jg_j(g_j+1)\tau_j/2 +
c_j/\tau_j\bigr)$ when, $\tau=\tau^*$ and, when the period of~$S$,
$T+2m$, is larger than $8m^2+(4\CC+1)m$.
\end{proofOf}

\subsection{Stretching lemma}

\begin{proofOf}{Lemma~\ref{lem:stretching}}
Note that the broadcast cost decreases from~$S$ to~$S'$. 

Consider a random request $Q$ for a message $M_i$ arriving in
$S'$. Let $\event_1$~denotes the event that $Q$~arrives outside the
new inserted slots, and $\event_2$~denotes the complementary event. we
have:
\begin{eqnarray*}
\expect[\ART(Q,S')] = &
&       \frac{\kappa}{\kappa+y} 
        \expect[\ART(Q,S')|\event_1]
\\
& + &   \frac{y}{\kappa+y} 
        \expect[\ART(Q,S')|\event_2]
\end{eqnarray*}

\textit{If $Q$ arrives in the new inserted slots}, then it will 
have to wait on average: 1) $y/2$ until the end of the empty slots; 2)
$\ART(S,M_i)-1/2$, since the slots are uniformly randomly
placed. Thus: $$
\begin{array}{r@~c@~l}
\expect[\ART(Q,S')|\event_2] 
& = & \DS\frac {y-1}2 + \ART(S,M_i) \\
& \leq &  y \ART(S,M_i)
\end{array}
$$
since $\ART(S,M_i)\geq 1/2$.

\textit{If $Q$ arrives outside the new inserted slots}, then let 
$Q_1$~the request arriving at the same time in the same slot
in~$S$. $Q_1$~is served on average after $\frac12+\ell$ slots, where
$\ell$~is the number of slots until the next broadcast of the
requested message. The expected response time to $Q$ in $S'$ is then
$1/2 + \expect[\ell']$, where $\ell'$ is the corresponding of $\ell$
in $S'$. On average, each ``inter-slot'' is increased on average
by~$y/\kappa$, thus: $\expect[\ell']=\ell+y/\kappa(\ell+1)$.  The
expected response time to $Q$ is $1/2+\ell\cdot (1+ \frac y\kappa) +
\frac y\kappa \leq \ART(Q_1,S) (1+\frac {2y}\kappa)$, which yields: $$
\expect[\ART(Q,S')|\event_1]
= \ART(S,M_i) \cdot (1+2y/\kappa) $$

Finally, by construction of~$\kappa$: 
$$
\begin{array}{r@~c@~l}
\expect[\ART(S',M_i)] 
%& \leq & \frac{\kappa}{\kappa+y} \ART(S,M_i) 
%                       \left(1+\frac{2y}\kappa\right)
%               + \frac{y}{\kappa+y} y \ART(S,M_i)\\
& \leq & (1+\epsilon) \ART(S,M_i)
\end{array}
$$
\end{proofOf}

\subsection{Mapping lemma}

\begin{proofOf}{Lemma~\ref{lem:mapping}}
Let $S_{\alpha W}$~the schedule obtained by scaling~$S$ by~$1/(\alpha
W)$. $S'$~is obtained by moving the broadcast of each message by at
most~$T$, thus the broadcast cost does not change and we just need to
bound the maximum increase of the expected response time a request.

Consider~$U>0$, and a message~$M_i$, let $\ell_1,\ldots,\ell_{p(U)}$
the intervals between the consecutive broadcasts of~$M_i$
in~$S_{\alpha W}$ up to time~$U$ ($\sum_k \ell_k=U$). The
intervals~$(\ell'_k)$ between consecutive broadcasts of~$M_i$ in~$S'$
are of the following form: $\ell'_k =\ell_k+x_k$, where $x_k\in[-T,T]$
and $\sum_k x_k=0$. Since, $$
\ART(S',M_i) = \limsup_{U\rightarrow\infty} 
        \frac1{2U} \sum_{k=1}^{p(U)} {\ell'_k}^2
$$ 
%
we have to bound: 
\begin{eqnarray*}
\frac1{2U} \sum_{k=1}^{p(U)} {\ell'_k}^2 & \leq & \frac1{2U} \left\{
        \sum_{k=1}^{p(U)} \ell_k^2 
        + \sum_{k=1}^{p(U)} x_k(2\ell_k+x_k) 
        \right\}\\
& \leq & \frac1{2U} \left\{ 
        \sum_{k=1}^{p(U)} \ell_k^2 
        + \sum_{k=1}^{p(U)} T (2\ell_k + x_k) \right.\\
& &     ~~~~~~~\left. + (x_{p(U)}-T)(2\ell_{p(U)} + x_{p(U)}) \right\}\\
& \leq & \frac1{2U} \sum_{k=1}^{p(U)} \ell_k^2 + T + 2T^2/U
\end{eqnarray*}
since for all~$k<p(u)$, $\ell_k\geq |\text{group of $M_i$}|/W\geq T$.

Thus, when $U$~goes to infinity, we get: $$
\ART(S',M_i) \leq \ART(S_{\alpha W},M_i) + T
$$ 
%
Lemma~\ref{lem:scaling}, and summing over the messages, yields then
the result.
\end{proofOf}

%\flushProofDeferred

\end{document}

cs0205012.extracted_bib
\begin{thebibliography}{10}

\bibitem{A98}
{\sc Acharya, S.}
\newblock {\em Broadcast Disks: Dissemination-based Management for Asymmetric
  Communication Environments}.
\newblock PhD thesis, Brown University, 1998.

\bibitem{A87}
{\sc Ammar, M.~H.}
\newblock Response time in a Teletext system: An individual user's perspective.
\newblock {\em IEEE Transactions on Communications COM-35,11\/} (Nov. 1987),
  1159--1170.

\bibitem{AW85}
{\sc Ammar, M.~H., and Wong, J.~W.}
\newblock The design of Teletext broadcast cycles.
\newblock In {\em Performance Evaluation\/} (1985), vol.~5(4), pp.~235--242.

\bibitem{AW87}
{\sc Ammar, M.~H., and Wong, J.~W.}
\newblock On the optimality of cyclic transmission in Teletext systems.
\newblock In {\em IEEE Trans. on Comm.\/} (1987), vol.~COM-35(11),
  pp.~1159--1170.

\bibitem{AGH98}
{\sc Anily, S., Glass, C.~A., and Hassin, R.}
\newblock The scheduling of maintenance service.
\newblock To appear (\textsf{http://www.math.tau.ac.il/$\sim$hassin}).

\bibitem{BBNS98}
{\sc Bar-Noy, A., Bhatia, R., Naor, J.~S., and Schieber, B.}
\newblock Minimizing service and operation costs of periodic scheduling.
\newblock In {\em Proc. of the 9th Annual ACM-SIAM Symp. on Discrete Algorithms
  (SODA)\/} (1998), pp.~11--20.

\bibitem{BC96}
{\sc Bestavros, A., and Cunha, C.}
\newblock Server-Initiated Document Dissemination for the WWW.
\newblock {\em IEEE Data Engineering Bulletin}, September 1996.

\bibitem{BS99}
{\sc Bar-Noy, A., and Shilo, Y.}
\newblock Optimal broadcasting of two files over an asymmetric channel.
\newblock In {\em Proc. of Infocom\/} (1999).

\bibitem{CC93}
{\sc Chan, M.~Y., and Chin, F.}
\newblock Schedulers for larger classes of pinwheel instances.
\newblock {\em Algorithmica 9\/} (Jun. 1993), 425--462.

\bibitem{G83}
{\sc Gecsei, J.}
\newblock The architecture of videotex systems.
\newblock {\em Prentice Hall, Englewood Cliffs, N.J.\/} (1983).

\bibitem{HW63}
{\sc Hadley, G., and Whitin, T.~M.}
\newblock {\em Analysis of inventory systems}.
\newblock Prentice-Hall, 1963.

\bibitem{HR87}
{\sc Hofri, M., and Rosberg, Z.}
\newblock Packet delay under the golden ratio weighted {TDM} policy in a
  multiple-access channel.
\newblock In {\em IEEE Trans. on Information Theory\/} (May 1987), vol.~11(33),
  pp.~341--349.

\bibitem{HMRTV89}
{\sc Holte, R., Mok, A., Rosier, L., Tulchinsky, I., and Varvel, D.}
\newblock The pinwheel: A real-time scheduling problem.
\newblock In {\em Proc. 22nd Hawaii Int. Conf. Syst. Sci.\/} (Jan. 1989),
  pp.~693--702.

\bibitem{IVB94}
{\sc Imielinski, T., Viswanathan, S., and Badrinath, B.}
\newblock Energy efficient indexing on air.
\newblock In {\em SIGMOD\/} (May 1994).

\bibitem{IR84}
{\sc Itai, A., and Rosberg, S.}
\newblock A golden ratio control policy for a multiple-access channel.
\newblock {\em IEEE Transactions on Autom. Contr. AC-29\/} (Aug. 1984).

\bibitem{KS99}
{\sc Kenyon, C., and Schabanel, N.}
\newblock The data broadcast problem with non-uniform transmission times.
\newblock In {\em Proc. of the 10th SODA\/} (1999), pp.~547--556.

\bibitem{KL98}
{\sc Khanna, S., and Liberatore, V.}
\newblock On broadcast disk paging.
\newblock In {\em Proceedings of 30th STOC\/} (1998), vol.~30, pp.~634--643.

\bibitem{KZ98}
{\sc Khanna, S., and Zhou, S.}
\newblock On indexed data broadcast.
\newblock In {\em Proceedings of 30th STOC\/} (1998), vol.~30, pp.~463--472.

\bibitem{S00}
{\sc Schabanel, N.}
\newblock The data broadcast problem with preemption.
\newblock In {\em LNCS Proc. of the 17th Symp. on Theor. Aspects of 
Comp. Sc. (STACS 2000)} (Feb. 2000, to be published).

\bibitem{SL96}
{\sc Shekhar, S., and Liu, D.}
\newblock Genesis: An approach to data dissemination in {A}dvanced {T}raveller
  {I}nformation {S}ystems ({ATIS}).
\newblock In {\em IEEE Data Engineering Bulletin\/} (Sept. 1996), vol.~19(3).

\bibitem{ST97}
{\sc Su, C.-J., and Tassiulas, L.}
\newblock Broadcast scheduling for information distribution.
\newblock In {\em Proc. of INFOCOM\/} (1997).

\bibitem{TX96}
{\sc Tan, K., and Xu, J.}
\newblock Energy efficient filtering of nonuniform broadcast.
\newblock In {\em Proc. of the 16\th~Int. Conf. in Distributed Computing
  System\/} (1996), pp.~520--527.

\bibitem{VH97}
{\sc Vaidya, N., and Hameed, S.}
\newblock Log time algorithms for scheduling single and multiple channel data
  broadcast.
\newblock In {\em Proc. of the 3rd ACM/IEEE Conf. on Mobile Computing and
  Networking (MOBICOM)\/} (Sep. 1997).

\bibitem{V94}
{\sc Vishwanath, S.}
\newblock {\em Publishing in wireless and wireline environments}.
\newblock PhD thesis, Rutgers University, 1994.


\end{thebibliography}