[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:11879 |
| Date | 07 July 2008 |
| Creators | MARCO SERPA MOLINARO |
| Contributors | EDUARDO SANY LABER |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0024 seconds