  $\newcommand{\cala}{\mathcal{A}}$ In MAXSPACE, given a set of ads $\cala$,
one wants to schedule a subset ${\cala'\subseteq\cala}$ into $K$ slots ${B_1,
\dots, B_K}$ of size $L$. Each ad ${A_i \in \cala}$ has a size $s_i$ and a
frequency $w_i$. A schedule is feasible if the total size of ads in any slot is
at most $L$, and each ad ${A_i \in \cala'}$ appears in exactly $w_i$ slots and
at most once per slot. The goal is to find a feasible schedule that maximizes
the sum of the space occupied by all slots. We consider a generalization called
MAXSPACE-R for which an ad $A_i$ also has a release date $r_i$ and may only
appear in a slot $B_j$ if ${j \ge r_i}$. For this variant, we give a
$1/9$-approximation algorithm. Furthermore, we consider MAXSPACE-RDV for which
an ad $A_i$ also has a deadline $d_i$ (and may only appear in a slot $B_j$ with
$r_i \le j \le d_i$), and a value $v_i$ that is the gain of each assigned copy
of $A_i$ (which can be unrelated to $s_i$). We present a polynomial-time
approximation scheme for this problem when $K$ is bounded by a constant. This
is the best factor one can expect since MAXSPACE is strongly NP-hard, even if
$K = 2$.
