Approximation algorithms for the MAXSPACE advertisement problem

Mauro R. C. da Silva; Lehilton L. C. Pedrosa; Rafael C. S. Schouery

paper

Approximation algorithms for the MAXSPACE advertisement problem

arXiv:2006.13430

Abstract

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 \geq 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} \leq j \leq 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$ .