A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem
Mauro R. C. da Silva, Rafael C. S. Schouery, Lehilton L. C. Pedrosa · Electronic Notes in Theoretical Computer Science · 2019
In the MAXSPACE problem, given a set of ads A , one wants to place a subset A ′ ⊆ A into K slots B 1 , ..., B K of size L . Each ad A i ∈ A 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 ∈ A ′ appears in exactly w i slots. The goal is to find a feasible schedule which maximizes the sum of the space occupied by all slots. We introduce a generalization, called MAXSPACE-RD, in which each ad A i also has a release date r i ≥ 1 and a deadline d i ≤ K , and may only appear in a slot B j with r i ≤ j ≤ d i . These parameters model situations where a subset of ads corresponds to a commercial campaign with an announcement date that may expire after some defined period. We present a polynomial-time approximation scheme for MAXSPACE-RD when K is bounded by a constant, i.e., for any ε > 0, we give a polynomial-time algorithm which returns a solution with value at least (1 −ε ) Opt , where Opt is the optimal value. This is the best factor one can expect, since MAXSPACE is NP-hard, even if K = 2.