Busca avançada
Ano de início
Entree


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

Texto completo
Autor(es):
Silva, Mauro Roberto Costa da
Número total de Autores: 1
Tipo de documento: Dissertação de Mestrado
Data de defesa:
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