{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:12Z","timestamp":1750220652253,"version":"3.41.0"},"reference-count":10,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Ministry of Science and Technology"},{"DOI":"10.13039\/501100003977","name":"Israeli Science Foundation","doi-asserted-by":"crossref","award":["573\/16"],"award-info":[{"award-number":["573\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012443","name":"BIU Center for Research in Applied Cryptography and Cyber Security","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012443","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["757731"],"award-info":[{"award-number":["757731"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>\n            The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain\n            <jats:italic>k<\/jats:italic>\n            memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times.\n          <\/jats:p>\n          <jats:p>\n            Bringmann, Doerr, Neumann, and Sliacan studied this problem as a special case of an online\/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all\n            <jats:italic>k<\/jats:italic>\n            and smaller than ln 4-o(1)\u2248 1.39 for the sparse subset of\n            <jats:italic>k<\/jats:italic>\n            \u2019s, which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            In this article, we solve the main problems left open in the above-mentioned paper by proving that ln 4 is a tight upper and lower bound on the asymptotic discrepancy for all large\n            <jats:italic>k<\/jats:italic>\n            and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et\u00a0al.) for all the small values of\n            <jats:italic>k<\/jats:italic>\n            \u2264 10.\n          <\/jats:p>\n          <jats:p>In the last part of the article, we describe some new applications of this online checkpointing problem.<\/jats:p>","DOI":"10.1145\/3379543","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Bounds on Online Checkpointing Algorithms"],"prefix":"10.1145","volume":"16","author":[{"given":"Achiya","family":"Bar-On","sequence":"first","affiliation":[{"name":"Department of Mathematics, Bar-Ilan University, Israel"}]},{"given":"Itai","family":"Dinur","sequence":"additional","affiliation":[{"name":"Computer Science Department, Ben-Gurion University, Israel"}]},{"given":"Orr","family":"Dunkelman","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Haifa, Israel"}]},{"given":"Rani","family":"Hod","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel Aviv University, Israel"}]},{"given":"Nathan","family":"Keller","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Bar-Ilan University, Israel"}]},{"given":"Eyal","family":"Ronen","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel Aviv University, Israel and Department of Electrical Engineering ESAT, KU Leuven, Belgium"}]},{"given":"Adi","family":"Shamir","sequence":"additional","affiliation":[{"name":"Computer Science Department, The Weizmann Institute, Israel"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9772-5"},{"key":"e_1_2_1_2_1","volume-title":"CVXOPT: A Python package for convex optimization. version 1.1.9.","author":"Andersen M. S.","year":"2016","unstructured":"M. S. Andersen , J. Dahl , and L. Vandenberghe . 2016 . CVXOPT: A Python package for convex optimization. version 1.1.9. Retrieved from http:\/\/cvxopt.org. M. S. Andersen, J. Dahl, and L. Vandenberghe. 2016. CVXOPT: A Python package for convex optimization. version 1.1.9. Retrieved from http:\/\/cvxopt.org."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294262"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933190"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_22"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009007"},{"volume-title":"Seminumerical Algorithms, by Donald Knuth","author":"Floyd Robert W.","key":"e_1_2_1_7_1","unstructured":"Robert W. Floyd . 1997. Cycle Finding Algorithm. Exercise 3.1\u20136 in The Art of Computer Programming , Vol. 2 : Seminumerical Algorithms, by Donald Knuth . Addison-Wesley . Robert W. Floyd. 1997. Cycle Finding Algorithm. Exercise 3.1\u20136 in The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, by Donald Knuth. Addison-Wesley."},{"key":"e_1_2_1_8_1","unstructured":"Free Software Foundation. 2012. GNU Linear Programming Kit. Version 4.61. Retrieved from http:\/\/www.gnu.org\/software\/glpk\/.  Free Software Foundation. 2012. GNU Linear Programming Kit. Version 4.61. Retrieved from http:\/\/www.gnu.org\/software\/glpk\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322131"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213039"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379543","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379543","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:23Z","timestamp":1750197743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379543"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3379543"],"URL":"https:\/\/doi.org\/10.1145\/3379543","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}