Approximation Algorithms for the MAXSPACE Advertisement Problem

In MAXSPACE, given a set of ads \(\mathcal {A}\) $\mathcal{A}$ , one wants to schedule a subset \({\mathcal {A}'\subseteq \mathcal {A}}\) ${\mathcal{A}}^{\prime }\subseteq \mathcal{A}$ into K slots \({B_1, \dots , B_K}\) $B_1,\cdots ,B_K$ of size L. Each ad  \({A_i \in \mathcal {A}}\) $A_i\in \mathcal{A}$ has a size  \(s_i\) $s_i$ and a frequency  \(w_i\) $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 \mathcal {A}'}\) $A_i\in {\mathcal{A}}^{\prime }$ appears in exactly \(w_i\) $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\) $A_i$ also has a release date  \(r_i\) $r_i$ and may only appear in a slot  \(B_j\) $B_j$ if \({j \ge r_i}\) $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\) $A_i$ also has a deadline  \(d_i\) $d_i$ (and may only appear in a slot  \(B_j\) $B_j$ with \(r_i \le j \le d_i\) $r_i\le j\le d_i$ ), and a value  \(v_i\) $v_i$ that is the gain of each assigned copy of  \(A_i\) $A_i$ (which can be unrelated to  \(s_i\) $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\) $K=2$ .