Logo PUC-Rio Logo Maxwell
ETDs @PUC-Rio
Estatística
Título: IMPROVED APPROXIMATIONS FOR THE K-HOTLINK ASSIGNMENT PROBLEM AND FOR BINARY SEARCHING IN TREES
Autor: MARCO SERPA MOLINARO
Colaborador(es): EDUARDO SANY LABER - Orientador
Catalogação: 07/JUL/2008 Língua(s): ENGLISH - UNITED STATES
Tipo: TEXT Subtipo: THESIS CONCURSO DE TESES E DISSERTAÇÕES 2009 - SBC
Notas: [pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
[en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio.
Referência(s): [pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=11879&idi=1
[en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=11879&idi=2
DOI: https://doi.org/10.17771/PUCRio.acad.11879
Resumo:
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.
Descrição: Arquivo:   
COVER, ACKNOWLEDGEMENTS, RESUMO, ABSTRACT AND SUMMARY PDF    
CHAPTER 1 PDF    
CHAPTER 2 PDF    
CHAPTER 3 PDF    
CHAPTER 4 PDF    
CHAPTER 5 PDF    
CHAPTER 6 PDF    
CHAPTER 7 PDF    
CHAPTER 8 PDF    
REFERENCES AND ANNEX PDF