Improved Approximations for the k-Hotlink Assignment Problem and for Binary Searching in Trees - Laber, Eduardo; Molinaro, Marco (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2009: Anais do XXII Concurso de Teses e Dissertações, 2009)
We present a study on two optimization problems in trees: the k-Hotlink Assignment Problem and the problem of Binary Searching in Trees. For the first problem we prove the existence of an FPTAS when k = 1, improving upon the constant factor algorithm recently obtained in [Jacobs, WADS 2007]. In addition, we develop the first constant factor approximation algorithm for arbitrary k. For the second problem we present a linear time algorithm which is the first to achieve a constant factor approximation. This represents a significant improvement over previous O(log n)-approximation. These results are included in Marco Molinaro’s master’s dissertation, submitted to and approved by the Departamento de Informática of PUC-RIO in 2008.