IMPROVED APPROXIMATIONS FOR THE K-HOTLINK ASSIGNMENT PROBLEM AND FOR BINARY SEARCHING IN TREES

[pt] Neste trabalho, apresentamos algoritmosaproximativos para dois problemas de otimizacao em arvores. Naprimeira parte, consideramos o Problema de Atribuicao dek-Hotlinks. Seja G= (V,E) um grafo direcionado aciclicorepresentando um web site, onde nos correspondem a paginas e arcoscorrespondem a hyperlinks. Nesse contexto, hotlink sao definidoscomo atalhos (novos arcos) adicionados as paginas de G de modo areduzir o tempo gasto pelos usuarios para alcancarem as informacoesdesejadas. Neste trabalho consideramos o problema onde G e umaarvore enraizada e o objetivo e minimizar o tempo medio gasto pelosusuarios atribuindo no maximo k hotlinks a cada no. Para a versaomais estudada desse problema onde no maximo um hotlink pode seratribuido a cada no, provamos a existencia de um FPTAS. Issorepresenta uma significante melhora em relacao ao algoritmo comaproximacao constante obtido recentemente em [Jacobs, WADS 2007].Alem disso, desenvolvemos o primeiro algoritmo com aproximacaoconstante para a versao mais geral onde k hotlinks podem seratribuidos a cada no. Na segunda parte deste trabalho, consideramoso problema de computar estrategias eficientes para realizar buscasem arvores. Como uma generalizacao da tradicional busca binaria emlistas ordenadas, suponha que se deseja encontrar um no especifico(porem desconhecido) de uma arvore realizando consultas em seusarcos, onde cada consulta indica a extremidade do arco mais proximaao no desejado. Dada a probabilidade de cada no ser aqueleprocurado, o objetivo e computar uma estrategia de busca queminimize o numero esperado de consultas. Aplicacoes praticas desseproblema incluem sincronizacao de file systems e testes desoftware. Apresentamos um algoritmo linear que obtem a primeiraaproximacao constante para esse problema. Isso representa umamelhora significativa em relacao a O(log n)-aproximacaoanterior.%%%%[en] Here we present a study on two optimizationproblems in trees: the k- Hotlink Assignment Problem and theproblem of Binary Searching in Trees. As a result, we obtainimproved approximation algorithms for both problem. The k-HotlinkAssignment Problem can be defined as follows. Let G = (V,E) be adirected acyclic graph representing a web site, where nodescorrespond to pages and arcs to hyperlinks. In this context,hotlinks are defined as shortcuts (new arcs) added to web pages ofG in order to reduce the time spent by users to reach their desiredinformation. Here we consider the problem where G is a rooteddirected tree and the goal is minimizing the expected time spent byusers by assigning at most k hotlinks to each node. For the moststudied version of this problem where at most one hotlink can beassigned from each node, we prove the existence of an FPTAS,improving upon the constant factor algorithm recently obtained in[Jacobs, WADS 2007]. In addition, we develop the first constantfactor approximation algorithm for the most general version where khotlinks can be assigned from each node. In the second part of thiswork, we consider the…