Improved Approximations for the k-Hotlink Assignment Problem and for Binary Searching in Trees
Resumo
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.
Referências
Adler, M., Demaine, E., Harvey, N., and Patrascu, M. (2006). Lower bounds for asymmetric communication channels and distributed source coding. In SODA, pages 251–260.
Adler, M. and Maggs, B. (2001). Protocols for asymmetric communication channels. Journal of Computer and System Sciences, 63(4):573–596.
Ben-Asher, Y., Farchi, E., and Newman, I. (1999). Optimal search in trees. SIAM Journal on Computing, 28(6):2090–2102.
Bose, P., Kranakis, E., Krizanc, D., Martin, M., Czyzowicz, J., Pelc, A., and Gasieniec, L. (2000). Strategies for hotlink assignments. In ISAAC, pages 23–34.
Carmo, R., Donadelli, J., Kohayakawa, Y., and Laber, E. (2004). Searching in random partially ordered sets. Theoretical Computer Science, 321(1):41–57.
Chakaravarthy, V., Pandit, V., Roy, S., Awasthi, P., and Mohania, M. (2007). Decision trees for entity identification: Approximation algorithms and hardness results. In PODS, pages 53–62.
Cicalese, F., Laber, E., and Molinaro, M. (2009). On the complexity of searching in trees: average-case minimization (in preparation).
Czyzowicz, J., Kranakis, E., Krizanc, D., Pelc, A., and Martin, M. (2003). Enhancing hyperlink structure for improving web performance. Journal of Web Engineering, 1(2):93–127.
de Prisco, R. and de Santis, A. (1993). On binary search trees. Information Processing Letters, 45(5):249–253.
Douïeb, K. and Langerman, S. (2005). Dynamic hotlinks. In WADS, pages 182–194.
Douïeb, K. and Langerman, S. (2006). Near-entropy hotlink assignments. In ESA, pages 292–303.
Gerstel, O., Kutten, S., Matichin, R., and Peleg, D. (2003). Hotlink enhancement algorithms for web directories: (extended abstract). In ISAAC, pages 68–77.
Jacobs, T. (2007). Constant factor approximations for the hotlink assignment problem. In WADS, pages 188–200.
Jacobs, T. (2008a). An experimental study of recent hotlink assignment algorithms. In ALENEX, pages 142–151.
Jacobs, T. (2008b). On the complexity of optimal hotlink assignment. In ESA, pages 540–552.
Knight, W. (1988). Search in an ordered array having variable probe cost. SIAM Journal on Computing, 17(6):1203–1214.
Knuth, D. (1998). The art of computer programming, volume 3: sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA.
Kosaraju, R., Przytycka, T., and Borgstrom, R. (1999). On an optimal split tree problem. In WADS, pages 157–168.
Kranakis, E., Krizanc, D., and Shende, S. M. (2004). Approximate hotlink assignment. Information Processing Letters, 90(3):121–128.
Kutten, S., Gerstel, O., Laber, E., Matichin, R., Peleg, D., Pessoa, A., and Souza, C. (2007). Reducing human interactions in web directory searches. ACM Transactions on Information Systems, (25).
Laber, E. and Holanda, L. (2002). Improved bounds for asymmetric communication protocols. Information Processing Letters, 83(4):205–209.
Laber, E., Milidiú, R., and Pessoa, A. (1999). Strategies for searching with different access costs. In ESA, pages 236–247.
Laber, E., Milidiú, R., and Pessoa, A. (2001). On binary searching with non-uniform costs. In SODA, pages 855–864.
Laber, E. and Nogueira, L. (2004). On the hardness of the minimum height decision tree problem. Discrete Applied Mathematics, 144(1-2):209–212.
Lipman, M. and Abrahams, J. (1995). Minimum average cost testing for partially ordered components. IEEE Transactions on Information Theory, 41(1):287–291.
Mozes, S., Onak, K., and Weimann, O. (2008). Finding an optimal tree searching strategy in linear time. In SODA, pages 1096–1105.
Onak, K. and Parys, P. (2006). Generalization of binary search: Searching in trees and forest-like partial orders. In FOCS, pages 379–388.
Perkowitz, M. and Etzioni, O. (1997). Adaptive web sites: an AI challenge. In IJCAI, pages 16–23.
Pessoa, A., Laber, E., and Souza, C. (2004). Efficient implementation of hotlink assignment algorithms for web sites. In ALENEX, pages 79–87.
Adler, M. and Maggs, B. (2001). Protocols for asymmetric communication channels. Journal of Computer and System Sciences, 63(4):573–596.
Ben-Asher, Y., Farchi, E., and Newman, I. (1999). Optimal search in trees. SIAM Journal on Computing, 28(6):2090–2102.
Bose, P., Kranakis, E., Krizanc, D., Martin, M., Czyzowicz, J., Pelc, A., and Gasieniec, L. (2000). Strategies for hotlink assignments. In ISAAC, pages 23–34.
Carmo, R., Donadelli, J., Kohayakawa, Y., and Laber, E. (2004). Searching in random partially ordered sets. Theoretical Computer Science, 321(1):41–57.
Chakaravarthy, V., Pandit, V., Roy, S., Awasthi, P., and Mohania, M. (2007). Decision trees for entity identification: Approximation algorithms and hardness results. In PODS, pages 53–62.
Cicalese, F., Laber, E., and Molinaro, M. (2009). On the complexity of searching in trees: average-case minimization (in preparation).
Czyzowicz, J., Kranakis, E., Krizanc, D., Pelc, A., and Martin, M. (2003). Enhancing hyperlink structure for improving web performance. Journal of Web Engineering, 1(2):93–127.
de Prisco, R. and de Santis, A. (1993). On binary search trees. Information Processing Letters, 45(5):249–253.
Douïeb, K. and Langerman, S. (2005). Dynamic hotlinks. In WADS, pages 182–194.
Douïeb, K. and Langerman, S. (2006). Near-entropy hotlink assignments. In ESA, pages 292–303.
Gerstel, O., Kutten, S., Matichin, R., and Peleg, D. (2003). Hotlink enhancement algorithms for web directories: (extended abstract). In ISAAC, pages 68–77.
Jacobs, T. (2007). Constant factor approximations for the hotlink assignment problem. In WADS, pages 188–200.
Jacobs, T. (2008a). An experimental study of recent hotlink assignment algorithms. In ALENEX, pages 142–151.
Jacobs, T. (2008b). On the complexity of optimal hotlink assignment. In ESA, pages 540–552.
Knight, W. (1988). Search in an ordered array having variable probe cost. SIAM Journal on Computing, 17(6):1203–1214.
Knuth, D. (1998). The art of computer programming, volume 3: sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA.
Kosaraju, R., Przytycka, T., and Borgstrom, R. (1999). On an optimal split tree problem. In WADS, pages 157–168.
Kranakis, E., Krizanc, D., and Shende, S. M. (2004). Approximate hotlink assignment. Information Processing Letters, 90(3):121–128.
Kutten, S., Gerstel, O., Laber, E., Matichin, R., Peleg, D., Pessoa, A., and Souza, C. (2007). Reducing human interactions in web directory searches. ACM Transactions on Information Systems, (25).
Laber, E. and Holanda, L. (2002). Improved bounds for asymmetric communication protocols. Information Processing Letters, 83(4):205–209.
Laber, E., Milidiú, R., and Pessoa, A. (1999). Strategies for searching with different access costs. In ESA, pages 236–247.
Laber, E., Milidiú, R., and Pessoa, A. (2001). On binary searching with non-uniform costs. In SODA, pages 855–864.
Laber, E. and Nogueira, L. (2004). On the hardness of the minimum height decision tree problem. Discrete Applied Mathematics, 144(1-2):209–212.
Lipman, M. and Abrahams, J. (1995). Minimum average cost testing for partially ordered components. IEEE Transactions on Information Theory, 41(1):287–291.
Mozes, S., Onak, K., and Weimann, O. (2008). Finding an optimal tree searching strategy in linear time. In SODA, pages 1096–1105.
Onak, K. and Parys, P. (2006). Generalization of binary search: Searching in trees and forest-like partial orders. In FOCS, pages 379–388.
Perkowitz, M. and Etzioni, O. (1997). Adaptive web sites: an AI challenge. In IJCAI, pages 16–23.
Pessoa, A., Laber, E., and Souza, C. (2004). Efficient implementation of hotlink assignment algorithms for web sites. In ALENEX, pages 79–87.
Publicado
20/07/2009
Como Citar
LABER, Eduardo; MOLINARO, Marco.
Improved Approximations for the k-Hotlink Assignment Problem and for Binary Searching in Trees. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 22. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 89-96.
ISSN 2763-8820.
