IMPROVED APPROXIMATIONS FOR THE K-HOTLINK ASSIGNMENT PROBLEM AND FOR BINARY SEARCHING IN TREES / ALGORITMOS APROXIMATIVOS PARA O PROBLEMA DE ATRIBUIÇÃO DE HOTLINKS E PARA BUSCA BINÁRIA EM ÁRVORES
AUTOR(ES)
MARCO SERPA MOLINARO
DATA DE PUBLICAÇÃO
2008
RESUMO
Neste trabalho, apresentamos algoritmos aproximativos para dois problemas de otimização em árvores. Na primeira parte, consideramos o Problema de Atribuição de k-Hotlinks. Seja G= (V,E) um grafo direcionado acíclico representando um web site, onde nós correspondem a páginas e arcos correspondem a hyperlinks. Nesse contexto, hotlink são definidos como atalhos (novos arcos) adicionados às páginas de G de modo a reduzir o tempo gasto pelos usuários para alcançarem as informações desejadas. Neste trabalho consideramos o problema onde G é uma árvore enraizada e o objetivo é minimizar o tempo médio gasto pelos usuários atribuindo no máximo k hotlinks a cada nó. Para a versão mais estudada desse problema onde no máximo um hotlink pode ser atribuído a cada nó, provamos a existência de um FPTAS. Isso representa uma significante melhora em relação ao algoritmo com aproximação constante obtido recentemente em [Jacobs, WADS 2007]. Além disso, desenvolvemos o primeiro algoritmo com aproximação constante para a versão mais geral onde k hotlinks podem ser atribuídos a cada nó. Na segunda parte deste trabalho, consideramos o problema de computar estratégias eficientes para realizar buscas em árvores. Como uma generalização da tradicional busca binária em listas ordenadas, suponha que se deseja encontrar um nó específico (porém desconhecido) de uma árvore realizando consultas em seus arcos, onde cada consulta indica a extremidade do arco mais próxima ao nó desejado. Dada a probabilidade de cada nó ser aquele procurado, o objetivo é computar uma estratégia de busca que minimize o número esperado de consultas. Aplicações práticas desse problema incluem sincronização de file systems e testes de software. Apresentamos um algoritmo linear que obtém a primeira aproximação constante para esse problema. Isso representa uma melhora significativa em relação à O(log n)-aproximação anterior.
ASSUNTO(S)
algoritmos aproximados busca search hotlinks hotlinks arvores trees approximation algorithms
