| Full text | |
| Author(s): |
da Silva, Mauro R. C.
;
Schouery, Rafael C. S.
;
Pedrosa, Lehilton L. C.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 12-pg., 2019-08-30. |
| Abstract | |
In the MAXSPACE problem, given a set of ads A, one wants to place a subset A' subset of A into K slots B-1, ..., B-K of size L. Each ad A(i) is an element of 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) is an element of 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 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 epsilon > 0, we give a polynomial-time algorithm which returns a solution with value at least (1 - epsilon)Opt, where Opt is the optimal value. This is the best factor one can expect, since MAXSPACE is NP-hard, even if K = 2. (AU) | |
| FAPESP's process: | 17/21297-2 - Advertisements scheduling problems |
| Grantee: | Mauro Roberto Costa da Silva |
| Support Opportunities: | Scholarships in Brazil - Master |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 16/23552-7 - Cutting and Packing Problems: Practical and Theoretical Approaches |
| Grantee: | Rafael Crivellari Saliba Schouery |
| Support Opportunities: | Regular Research Grants |