Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/334320
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Heurísticas e algoritmos de aproximação para problemas de disposição de propagandas
Title Alternative: Heuristics and approximation algorithms for scheduling advertisements problem
Author: Silva, Mauro Roberto Costa da, 1995-
Advisor: Schouery, Rafael Crivellari Saliba, 1986-
Abstract: 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

Abstract: In the MAXSPACE problem, given a set of ads A, one wants to place a subset A' of A into K slots B_1, ..., B_K of size L. Each advertisement A_i in 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 in A' appears in exactly w_i slots with at most one copy per slot. The objective is to find a feasible schedule which maximizes the sum of the space occupied by all slots. We introduce some generalizations for this problem, such as MAXSPACE-R, MAXSPACE-RD, and MAXSPACE-RDWV. We consider the MAXSPACE-RD with a constant number of slots and present a polynomial-time approximation scheme, i.e., for any ? > 0, we give a polynomial-time algorithm which returns a solution with value at least (1-?)OPT, where OPT is the optimal value. We also present a 1/9-approximation for MAXSPACE-R with a polynomial number of slots. We implement the metaheuristics Greedy Randomized Adaptive Search Procedure, Variable Neighborhood Search, Variable Neighborhood Descent, Tabu Search and Local Search for MAXSPACE and MAXSPACE-RDWV. The computational results of these heuristics were compared with the results of the hybrid genetic algorithm proposed by Kumar et al
Subject: Meta-heurística
Algoritmos de aproximação
Teoria da computação
Language: Português
Editor: [s.n.]
Citation: SILVA, Mauro Roberto Costa da. Heurísticas e algoritmos de aproximação para problemas de disposição de propagandas. 2019. 1 recurso online (67 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2019
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Silva_MauroRobertoCostaDa_M.pdf2.47 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.