{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:12Z","timestamp":1750306752875,"version":"3.41.0"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,7,1]],"date-time":"2013-07-01T00:00:00Z","timestamp":1372636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WE 2842\/1"],"award-info":[{"award-number":["WE 2842\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Centre for Discrete Mathematics and its Applications"},{"name":"UMIC Research Centre"},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/D063191\/1, EP\/F043333\/1"],"award-info":[{"award-number":["EP\/D063191\/1, EP\/F043333\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007210","name":"RWTH Aachen University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007210","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>\n            We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain capacity. For each time step, an online algorithm is given a price from the interval [1,\n            <jats:italic>\u03b1<\/jats:italic>\n            ], a consumption, and possibly a buying limit. The online algorithm has to decide the amount to purchase from some commodity, knowing the parameter\n            <jats:italic>\u03b1<\/jats:italic>\n            but without knowing how the price evolves in the future. The algorithm can purchase at most the buying limit. If it purchases more than the current consumption, then the excess is stored in the storage; otherwise, the gap between consumption and purchase must be taken from the storage. The goal is to minimize the total cost. Interesting motivating applications are, for example, stream caching on mobile devices with different classes of service, battery management in micro hybrid cars, and the efficient purchase of resources.\n          <\/jats:p>\n          <jats:p>\n            First we consider the simple but natural class of algorithms that can informally be described as memoryless. We show that these algorithms cannot achieve a competitive ratio below \u221a\n            <jats:italic>\u03b1<\/jats:italic>\n            . Then we present a more sophisticated deterministic algorithm achieving a competitive ratio of where\n            <jats:italic>W<\/jats:italic>\n            denotes the Lambert W function. We prove that this algorithm is optimal and that not even randomized online algorithms can achieve a better competitive ratio. On the other hand, we show how to achieve a constant competitive ratio if the storage capacity of the online algorithm exceeds the storage capacity of an optimal offline algorithm by a factor of log\n            <jats:italic>\u03b1<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2493246.2493247","type":"journal-article","created":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T19:12:41Z","timestamp":1374779561000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Economical Caching"],"prefix":"10.1145","volume":"5","author":[{"given":"Matthias","family":"Englert","sequence":"first","affiliation":[{"name":"University of Warwick"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[{"name":"University of Bonn"}]},{"given":"Jacob","family":"Sp\u00f6nemann","sequence":"additional","affiliation":[{"name":"RWTH Aachen University"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[{"name":"RWTH Aachen University"}]}],"member":"320","published-online":{"date-parts":[[2013,7]]},"reference":[{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.485708"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/274440.274442"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1814087.1814106"},{"volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201910)","year":"2010","author":"Geulen Sascha","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 13th International Coriference on Machine Learning (ICML\u201996)","author":"Helmbold David P.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/238061.238161"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493246.2493247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2493246.2493247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:32Z","timestamp":1750231712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493246.2493247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":8,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.1145\/2493246.2493247"],"URL":"https:\/\/doi.org\/10.1145\/2493246.2493247","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2013,7]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}