Texto completo
| |
| Autor(es): |
Mauro Roberto Costa da Silva
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2019-03-20 |
| Membros da banca: |
Rafael Crivellari Saliba Schouery;
Kelly Cristina Poldi;
Eduardo Candido Xavier
|
| Orientador: | Rafael Crivellari Saliba Schouery; Lehilton Lelis Chaves Pedrosa |
| 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 |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |