{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:12Z","timestamp":1750220292172,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62002394"],"award-info":[{"award-number":["62002394"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research Grants Council, Hong Kong, China","award":["16200317"],"award-info":[{"award-number":["16200317"]}]},{"name":"ERC","award":["StG 757609"],"award-info":[{"award-number":["StG 757609"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            Ailon\u00a0et\u00a0al.\u00a0[SICOMP\u201911] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , ... ,\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            follow some unknown\n            <jats:italic>product distribution<\/jats:italic>\n            . That is,\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            is drawn independently from a fixed unknown distribution \ud835\udc9f\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            . After spending\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03b5<\/jats:sup>\n            ) time in a learning phase, the subsequent expected running time is\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>H<\/jats:italic>\n            )\/\u03b5), where\n            <jats:italic>H<\/jats:italic>\n            \u220a {\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>S<\/jats:sub>\n            ,\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>DT<\/jats:sub>\n            }, and\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>S<\/jats:sub>\n            and\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>DT<\/jats:sub>\n            are the entropies of the distributions of the sorting and DT output, respectively. In this article, we allow dependence among the\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2019s under the\n            <jats:italic>group product distribution<\/jats:italic>\n            . There is a hidden partition of [1,\n            <jats:italic>n<\/jats:italic>\n            ] into groups; the\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2019s in the\n            <jats:italic>k<\/jats:italic>\n            th group are fixed unknown functions of the same hidden variable\n            <jats:italic>\n              u\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            ; and the\n            <jats:italic>\n              u\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            \u2019s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map\n            <jats:italic>\n              u\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            to\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2019s are well-behaved. After an\n            <jats:italic>O<\/jats:italic>\n            (poly(\n            <jats:italic>n<\/jats:italic>\n            ))-time training phase, we achieve\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>S<\/jats:sub>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u03b1 (\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>DT<\/jats:sub>\n            ) expected running times for sorting and DT, respectively, where \u03b1 (\u22c5) is the inverse Ackermann function.\n          <\/jats:p>","DOI":"10.1145\/3531227","type":"journal-article","created":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T11:55:13Z","timestamp":1651060513000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Generalization of Self-Improving Algorithms"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3720-5117","authenticated-orcid":false,"given":"Kai","family":"Jin","sequence":"first","affiliation":[{"name":"School of Intelligent Systems Engineering, Sun Yat-Sen University, Shen Zhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3557-9935","authenticated-orcid":false,"given":"Siu-Wing","family":"Cheng","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, HKUST, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7435-1020","authenticated-orcid":false,"given":"Man-Kwun","family":"Chiu","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5682-0003","authenticated-orcid":false,"given":"Man Ting","family":"Wong","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, HKUST, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/090766437"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944347"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9785-3"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221041"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0939-8"},{"key":"e_1_3_3_8_2","first-page":"29:1\u201329:13","volume-title":"Proceedings of the 36th Symposium on Computational Geometry","author":"Cheng S.-W.","year":"2020","unstructured":"S.-W. Cheng, M.-K. Chiu, K. Jin, and M. T. Wong. 2020. A generalization of self-improving algorithms. In Proceedings of the 36th Symposium on Computational Geometry. 29:1\u201329:13."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00604-6"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/12089702X"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"e_1_3_3_12_2","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Riviest, and C. Stein. 2009. Introduction to Algorithms. MIT Press."},{"key":"e_1_3_3_13_2","volume-title":"Elements of Information Theory (2 ed.)","author":"Cover T. M.","year":"2006","unstructured":"T. M. Cover and J. A. Thomas. 2006. Elements of Information Theory (2 ed.). Wiley-Interscience, New York."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35651-8"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219053"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803774"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.010"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.0095"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/010\/0113289"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264563"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:31Z","timestamp":1750188691000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3531227"],"URL":"https:\/\/doi.org\/10.1145\/3531227","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2020-08-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}