Heurísticas e algoritmos de aproximação para problemas de disposição de propagandas

Autor(es)

Silva, Mauro Roberto Costa da

• Tipo de documento: Dissertação de Mestrado
• Data de defesa: 2019

Resumo

No problema MAXSPACE, dado um conjunto de propagandas A, desejamos dispor um subconjunto A' de A em K slots B_1, ..., B_K de tamanho L. Cada propaganda A_i em 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 em 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 esse problema, como o MAXSPACE-R, o MAXSPACE-RD e o MAXSPACE-RDWV. Consideramos o problema MAXSPACE-RD com número de slots constante e apresentamos um esquema de aproximação polinomial, isto é, para qualquer ? > 0, damos um algoritmo de tempo polinomial que devolve uma solução com valor pelo menos (1-?)OPT, em que OPT é o valor de um solução ótima. Também apresentamos uma 1/9-aproximação para o MAXSPACE-R com K polinomialmente limitado. 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 (AU)

• Processo FAPESP: 17/21297-2 - Problemas de disposição de propagandas
• Beneficiário: Mauro Roberto Costa da Silva
• Linha de fomento: Bolsas no Brasil - Mestrado