{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:43Z","timestamp":1759063543887,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/100.505\/2007"],"award-info":[{"award-number":["E-26\/100.505\/2007"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["304786\/2006-3470654\/2007-4"],"award-info":[{"award-number":["304786\/2006-3470654\/2007-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V,E<\/jats:italic>\n            ) be a 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\n            <jats:italic>G<\/jats:italic>\n            in order to reduce the time spent by users to reach their desired information. In this article, we consider the problem where\n            <jats:italic>G<\/jats:italic>\n            is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most\n            <jats:italic>k<\/jats:italic>\n            hotlinks to each node.\n          <\/jats:p>\n          <jats:p>\n            For the most studied version of this problem where at most one hotlink can be added to each node, we prove the existence of two FPTAS's which optimize different objectives considered in the literature: one minimizes the expected user path length and the other maximizes the expected reduction in user path lengths. These results improve over a constant factor approximation for the expected length and over a PTAS for the expected reduction, both obtained recently in Jacobs [2007]. Indeed, these FPTAS's are essentially the best possible results one can achieve under the assumption that\n            <jats:italic>P<\/jats:italic>\n            \u2260\n            <jats:italic>NP<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Another contribution we give here is a 16-approximation algorithm for the most general version of the problem where up to\n            <jats:italic>k<\/jats:italic>\n            hotlinks can be assigned from each node. This algorithm runs in\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>V<\/jats:italic>\n            | log |\n            <jats:italic>V<\/jats:italic>\n            |) time and it turns to be the first algorithm with constant approximation for this problem.\n          <\/jats:p>","DOI":"10.1145\/1978782.1978794","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved approximations for the hotlink assignment problem"],"prefix":"10.1145","volume":"7","author":[{"given":"Eduardo","family":"Laber","sequence":"first","affiliation":[{"name":"PUC-Rio, Gavea-Rio de Janeiro, RJ-Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1779"},{"volume-title":"Proceedings of the International Symposium on Algorithms and Computation. 23--34","author":"Bose P.","key":"e_1_2_1_2_1","unstructured":"Bose , P. , Kranakis , E. , Krizanc , D. , Martin , M. , Czyzowicz , J. , Pelc , A. , and Gasieniec , L . 2000. Strategies for hotlink assignments . In Proceedings of the International Symposium on Algorithms and Computation. 23--34 . Bose, P., Kranakis, E., Krizanc, D., Martin, M., Czyzowicz, J., Pelc, A., and Gasieniec, L. 2000. Strategies for hotlink assignments. In Proceedings of the International Symposium on Algorithms and Computation. 23--34."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1126-2"},{"key":"e_1_2_1_4_1","first-page":"93","article-title":"Enhancing hyperlink structure for improving web performance","volume":"1","author":"Czyzowicz J.","year":"2003","unstructured":"Czyzowicz , J. , Kranakis , E. , Krizanc , D. , Pelc , A. , and Martin , M. 2003 . Enhancing hyperlink structure for improving web performance . J. Web Engin. 1 , 2, 93 -- 127 . Czyzowicz, J., Kranakis, E., Krizanc, D., Pelc, A., and Martin, M. 2003. Enhancing hyperlink structure for improving web performance. J. Web Engin. 1, 2, 93--127.","journal-title":"J. Web Engin."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_17"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_28"},{"volume-title":"Information Theory and Reliable Communication","author":"Gallager R.","key":"e_1_2_1_7_1","unstructured":"Gallager , R. 1968. Information Theory and Reliable Communication . John Wiley & Sons , New York Gallager, R. 1968. Information Theory and Reliable Communication. John Wiley & Sons, New York"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Gerstel O. Kutten S. Matichin R. and \n      Peleg D\n  . \n  2003\n  . Hotlink enhancement algorithms for web directories: (extended abstract). In Proceedings of the International Symposium on Algorithms and Computation (ISAAC) T. Ibaraki N. Katoh and H. Ono Eds. Lecture Notes in Computer Science vol. \n  2906 Springer 68--77.  Gerstel O. Kutten S. Matichin R. and Peleg D. 2003. Hotlink enhancement algorithms for web directories: (extended abstract). In Proceedings of the International Symposium on Algorithms and Computation (ISAAC) T. Ibaraki N. Katoh and H. Ono Eds. Lecture Notes in Computer Science vol. 2906 Springer 68--77.","DOI":"10.1007\/978-3-540-24587-2_9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394893.2394917"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972887.14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_45"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_64"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281485.1281491"},{"volume-title":"Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO). 233--244","author":"Matichin R.","key":"e_1_2_1_14_1","unstructured":"Matichin , R. and Peleg , D . 2004. Approximation algorithm for hotlink assignment in the greedy model . In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO). 233--244 . Matichin, R. and Peleg, D. 2004. Approximation algorithm for hotlink assignment in the greedy model. In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO). 233--244."},{"volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI) (1). 16--23","author":"Perkowitz M.","key":"e_1_2_1_15_1","unstructured":"Perkowitz , M. and Etzioni , O . 1997. Adaptive web sites: an AI challenge . In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI) (1). 16--23 . Perkowitz, M. and Etzioni, O. 1997. Adaptive web sites: an AI challenge. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI) (1). 16--23."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_67"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX\/ANALC). 79--87","author":"Pessoa A. A.","year":"2004","unstructured":"Pessoa , A. A. , Laber , E. S. , and de Souza , C. 2004 b. Efficient implementation of hotlink assignment algorithm for web sites . In Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX\/ANALC). 79--87 . Pessoa, A. A., Laber, E. S., and de Souza, C. 2004b. Efficient implementation of hotlink assignment algorithm for web sites. In Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX\/ANALC). 79--87."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978794","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1978782.1978794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:37Z","timestamp":1750244377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1978782.1978794"],"URL":"https:\/\/doi.org\/10.1145\/1978782.1978794","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}