[pt] 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. / [en] Here we present a study on two optimization problems in trees: the k- Hotlink Assignment Problem and the problem of Binary Searching in Trees. As a result, we obtain improved approximation algorithms for both problem. The k-Hotlink Assignment Problem can be defined as follows. Let G = (V,E) be a directed acyclic graph representing a web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to web pages of G in order to reduce the time spent by users to reach their desired information. Here we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be assigned 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 constant factor approximation algorithm for the most general version where k hotlinks can be assigned from each node. In the second part of this work, we consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.

[pt] Uma maneira de localizar uma informação em uma base de dados grande e caótica como a Internet é utilizar um índice hierárquico que respeita alguma maneira de categorizar os dados. Exemplos desta hierarquia são os serviços de diretório, comuns em sites de busca. Porém, esta abordagem pode apresentar algumas desvantagens, como a necessidade de percorrer muitas páginas até chegar em uma informação muito acessada. Uma maneira de tratar este problema é o uso de hotlinks, hyperlinks adicionais que servem como atalho em uma busca. Estudamos algoritmos eficientes para atribuir hotlinks em um diretório web, de modo a reduzir o número máximo ou o número médio de acessos em uma busca. Fornecemos para o problema de minimização do número máximo de acessos um algoritmo (14/3)-aproximado e um algoritmo polinomial exato baseado em programação dinâmica. Por outro lado, para o problema de minimizar o número médio de acessos, adaptamos o algoritmo exato do problema anterior. Entretanto, este algoritmo adaptado é polinomial apenas para sites representados por árvores com altura O(log n). Por isso, introduzimos um parâmetro que permite ao usuário reduzir o tempo de execução em detrimento da qualidade da solução. Para este problema de minimizar o número médio de acessos, realizamos também experimentos comparando nosso algoritmo, um modelo em programação inteira, e alguns algoritmos propostos por outros autores. Introduzimos modificações práticas que melhoraram a performance do nosso algoritmo. / [en] An approach to search an information in a large and chaotic data base like the Internet is to use a hierarquical index regarding some categorization of the data. As an example, we have the web directories, usually found in search engines. However, this approach may have problems, as the need of visiting too many web pages to find a very accessed information. A way to address this problem is the use of hotlinks, which are hyperlinks added to the web site and used as shortcuts in a search. We studied efficient algorithms to assign hotlinks in web directories, in such a way to minimize the maximum or the average number of accesses to find an information. For the problem of minimizing the maximum number of accesses, we provide an (14/3)-approximation algorithm and an exact polinomial time algorithm based on dynamic programming. On the other hand, for the problem of minimizing the expected number of accesses, we adapted the previous exact algorithm. However, this adapted algorithm is polinomial only for web sites represented by trees with height O(log n). So, we introduce a parameter that allows the user to reduce the execution time under the cost of reducing the solution quality. For this problem of minimizing the expected number of accesses, we also made experiments comparing our algorithm, an integer programming model, and some algorithms proposed by other authors. We introduce pratical changes that improved the performance of our algorithm.

[pt] Consideramos dois problemas de otimização combinatória: o problema de transporte em redes de dutos (PTD) e o problema de busca com custos de acesso variados (PBC). No PTD, é dado um grafo orientado G = (N,A) onde cada arco tem um duto associado. Também é dado um conjunto de bateladas, onde cada batelada está inicialmente em um nó ou arco do grafo e tem um nó de destino. Algumas bateladas são chamadas de proteláveis. O objetivo do PTD é encontrar uma sequência de operações que transporte todas as bateladas não-proteláveis aos seus respectivos nós de destino. Primeiro, demonstramos o PTD é NP-difícil, mesmo que o grafo G seja acíclico. Em seguida, apresentamos um algoritmo polinomial chamado de BPA. Este algoritmo resolve o PTDS, uma variação do PTD, para qualquer grafo G. Para grafos acíclicos, o BPA minimiza uma função de custo genérica. Para minimizar o makespan no PTDS, demonstramos que não existe algoritmo polinomial n1-e - aproximado para nenhum E>0, a menos que P = NP, onde n é o tamanho da instância. Este resultado também vale se G é acíclico e planar. No PBC, são dados um vetor ordenado e o custo de acessar cada um de seus n elementos. O objetivo do problema é encontrar uma estratégia de busca que minimize o custo médio com probabilidades uniformes (PBCM) ou o custo do pior caso (PBCN). Em ambos os casos, o melhor algoritmo exato conhecido executa em tempo O(n3) e espaço O(n2). Para o PBCN, apresentamos o algoritmo da razão, que executa em tempo O(n2) e espaço O(n). Este algoritmo sempre obtém uma solução de custo menor ou igual a 41n(n+1)/n, assumindo que a soma dos custos é 1. Além disso, desenvolvemos dois algoritmos aproximados: um para o PBCM e outro para o PBPC. Ambos constroem soluções (2+E+0(1)) - aproximadas, para qualquer E>0, em tempo e espaço O(n). / [en] We consider two combinatorial optimization problems the pipeline transportation problem (PTD) and the problem of searching with different access costs (PBC). In PTD, we are given a directed graph G = (N,A) where each arc corresponds to a pipeline. We are also given a set of batches, each batch being initially located at an arc or node and having a destination node. A subset of these batches are considered as further batches. Our aim is to find a sequence of pipeline operations leading all non-further batches to their corresponding destination nodes. First, we show that PDT is NP-hard, even for the case where G is acyclic. Next, we present a polynomial algorithm called BPA. This algorithm solves PTDS, a variation of PTD, for general graphs. For acyclic graphs, BPA also minimizes a general cost function. For the case of makespan minimization for PTDS, we prove that there is no n1-e - approximate algorithm for any E]0, unless P = NP, where n is the instance size. The previous result also holds if G is both ayclic and planar. In PBC, we are given an ordered vector with n elements and the corresponding access costs. Our aim is to find a search strategy that minimizes either the average cost (PBPC). In both cases, the best known exact algorithm requires in O(n3) time and O(n2) space. For PBCM, we present the ratio algorithm, that requires O(n2) time and O(n3)space. This algorithm always obtains a search strategy with average cost at most 41n(n+1)/n, assuming the sum of all access costs to be 1. Furthermore, we introduce approximation algorithms for both PBCM and PBPC. Both of them give (2+E+0(1)) - approximate solutions, for any E}0, in O(n) time and space.