A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem

• Published in: Electronic notes in theoretical computer science 2019-08, Vol.346, p.699-710
• Main Authors: da Silva, Mauro R.C., Schouery, Rafael C.S., Pedrosa, Lehilton L.C.
• Format: Article
• Language: English
• Subjects: Approximation Algorithm; MAXSPACE; PTAS; Scheduling of Advertisements
• ISSN: 1571-0661; 1571-0661
• DOI: 10.1016/j.entcs.2019.08.061

In the MAXSPACE problem, given a set of ads A, one wants to place a subset A′⊆A into K slots B1, ..., BK of size L. Each ad Ai∈A has a size si and a frequency wi. A schedule is feasible if the total size of ads in any slot is at most L, and each ad Ai∈A′ appears in exactly wi 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 Ai also has a release date ri ≥ 1 and a deadline di ≤ K, and may only appear in a slot Bj with ri ≤ j ≤ di. 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.