Defesa de Mestrado de Mauro Roberto Costa da Silva

Título do Trabalho
Heurísticas e Algoritmos de Aproximação para Problemas de Disposição de Propagandas
Candidato(a)
Mauro Roberto Costa da Silva
Nível
Mestrado
Data
Add to Calender 2019-03-20 00:00:00 2019-03-20 00:00:00 Defesa de Mestrado de Mauro Roberto Costa da Silva Heurísticas e Algoritmos de Aproximação para Problemas de Disposição de Propagandas Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 85 IC 2
Orientador(a)
Rafael Crivellari Saliba Schouery
Banca Examinadora

* Titulares

Unidade/Instituição

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Kelly Cristina Poldi

IMECC/UNICAMP

Eduardo Candido Xavier

IC/UNICAMP

* Suplentes

Unidade/Instituição

Fábio Luiz Usberti

IC/UNICAMP

Pedro Henrique Del Bianco Hokama

IMC/UNIFEI

Resumo

No problema MAXSPACE, dado um conjunto de propagandas A, desejamos dispor um subconjunto A’ ⊆ A em K slots B_1,..., B_K de tamanho L. Cada propaganda A_i ∈ A tem um tamanho s_i e uma frequência w_i. Uma disposição é viável se o tamanho total das propagandas em qualquer slot é no máximo L e cada A_i ∈ A’ aparece em exatamente w_i slots e no máximo uma vez por slot. O objetivo é encontrar uma disposição viável que maximiza a soma dos espaços ocupados por todos os slots.

Introduzimos algumas variantes para o problema, como o MAXSPACE-R, o MAXSPACE-RD e o MAXSPACE-RDWV. No MAXSPACE-R, cada propaganda A_i possui um release date r_i ≥ 1 e pode apenas aparecer em slots B_j com r_i ≤ j. O MAXSPACE-RD é uma generalização do MAXSPACE-R, e nele cada propaganda A_i também possui um deadline d_i ≤ K e pode apenas aparecer em slots B_j com r_i ≤ j ≤ d_i. Esses parâmetros modelam situações em que um subconjunto de propagandas correspondem a uma campanha comercial com data de início e que deve terminar após algum período definido. Já o MAXSPACE-RDWV é uma generalização do MAXSPACE-RD, e nele cada propanganda Ai também possui um valor v_i, uma frequência variável dada por w_i^min e w_i^max e deve ser disposta em pelo menos w_i^min slots e no máximo em w_i^max slots. O valor v_i indica a quantia arrecadada por cada cópia de A_i disposta. No MAXSPACE-RDWV o objetivo é encontrar uma disposição viável que maximiza o valor das propagandas dispostas.

Consideramos os problemas MAXSPACE-R e MAXSPACE-RD com número de slots constantes e apresentamos um polynomial-time approximation scheme para cada problema, isto é, para qualquer ε > 0, damos um algoritmo em tempo polinomial que devolve uma solução com valor pelo menos (1 − ε)OPT, em que OPT é o valor de um solução ótima. Esse é o melhor fator que podemos esperar, dado que o MAXSPACE é NP-difícil até para K = 2. Também apresentamos uma 1/9-aproximação para o MAXSPACE-R com K polinomialmente limitado.

Também abordamos os problemas MAXSPACE e MAXSPACE-RDWV do ponto de vista de heurísticas, utilizando as meta-heurísticas Greedy Randomized Adaptive Search Procedure, Variable Neighborhood Search, Variable Neighborhood Descent, Busca Tabu e Busca Local. Os resultados computacionais das heurísticas implementadas foram comparados com o algoritmo genético híbrido proposto por Kumar et al.