Busca avançada
Ano de início
Entree


A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem

Texto completo
Autor(es):
da Silva, Mauro R. C. ; Schouery, Rafael C. S. ; Pedrosa, Lehilton L. C.
Número total de Autores: 3
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