[pt] AVALIAÇÃO DE ALGORITMOS ONLINE PARA SELEÇÃO DE LINKS PATROCINADOS - LUIZ FERNANDO FERNANDES DE ALBUQUERQUE (2010)
[pt] Links patrocinados são aqueles que aparecem em destaque nos resultados de pesquisas em máquinas de busca na Internet e são grande fonte de receita para seus provedores. Para os anunciantes, que fazem ofertas por palavras-chave para aparecerem em destaque nas consultas dos usuários, são uma oportunidade de divulgação da marca, conquista e manutenção de clientes. Um dos desafios das máquinas de busca neste modelo de negócio é selecionar os anunciantes que serão exibidos a cada consulta de modo a maximizar sua receita em determinado período. Este é um problema tipicamente online, onde a cada consulta é tomada uma decisão sem o conhecimento prévio das próximas consultas. Após uma decisão ser tomada, esta não pode mais ser alterada. Nesta dissertação avaliamos experimentalmente algoritmos propostos na literatura para solução deste problema, comparando-os à solução ótima offline, em simulações com dados sintéticos. Supondo que o conjunto das consultas diárias obedeça a uma determinada distribuição, propomos dois algoritmos baseados em informações estocásticas que são avaliados nos mesmos cenários que os outros algoritmos.