Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 12-pg., 2019-08-30.

Resumo

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)

• Processo FAPESP: 17/21297-2 - Problemas de disposição de propagandas
• Beneficiário: Mauro Roberto Costa da Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas
• Beneficiário: Rafael Crivellari Saliba Schouery
• Modalidade de apoio: Auxílio à Pesquisa - Regular