{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:54Z","timestamp":1787323374277,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Open Internet Consortium"},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["497\/14"],"award-info":[{"award-number":["497\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006260","name":"Technion-Israel Institute of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006260","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The dynamic content distribution problem addresses the trade-off between storage and delivery costs in modern virtual content delivery networks (CDNs). That is, a video file can be stored in multiple places so that the request of each user is served from a location that is near the user. This minimizes the delivery costs, but is associated with a storage cost. This problem is NP-hard even in grid networks. In this paper, we present a constant factor approximation algorithm for grid networks. We also present an $O(\\log \\delta)$-competitive algorithm, where $\\delta$ is the normalized diameter of the network, for general networks with general metrics. We show a matching lower bound by using a reduction from online undirected Steiner tree. Our algorithms use a rather intuitive approach that has an elegant representation in geometric terms.<\/jats:p>","DOI":"10.1137\/16m1103014","type":"journal-article","created":{"date-parts":[[2018,8,1]],"date-time":"2018-08-01T12:34:58Z","timestamp":1533126898000},"page":"1903-1921","source":"Crossref","is-referenced-by-count":1,"title":["Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks"],"prefix":"10.1137","volume":"32","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erez","family":"Kantor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,1]]},"reference":[{"key":"atypb1","first-page":"2020","author":"Networking Index Cisco Visual","year":"2015","journal-title":"Forecast and Methodology"},{"key":"atypb2","first-page":"2020","author":"Networking Index Cisco Visual","year":"2015","journal-title":"Global Mobile Data Traffic Forecast Update"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"J. C. Abell,\n                      Netflix instant account for 20 percent of peak U.S. bandwidth use\n                      . Wire magazine, October 21, 2010.","DOI":"10.2469\/cfm.v21.n5.12"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573969"},{"key":"atypb5","first-page":"164","author":"Awerbuch B.","year":"1993","journal-title":"New York"},{"key":"atypb6","first-page":"39","author":"Bartal Y.","year":"1992","journal-title":"New York"},{"key":"atypb7","first-page":"344","author":"Berman P.","year":"1997","journal-title":"New York"},{"key":"atypb8","unstructured":"D. Black and D. Sleator,\n                      Competitive Algorithms for Replication and Migration Problems\n                      , Technical report CMU-CS-89-201, Carnegie Mellon University, Pittsburgh, PA, 1989."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"atypb10","first-page":"410","author":"Charikar M.","year":"1998","journal-title":"Philadelphia"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(02)00251-7"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/356876.356883"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220105"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"atypb16","unstructured":"D. Jones,\n                      Proof that Telstra is Throttling YouTube Bandwidth in Australia\n                      ,http:\/\/www.youtube.com\/watch?v=9iDRynyBl0c(2010)."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0140-3664(01)00409-1"},{"key":"atypb18","first-page":"520","author":"Kantor E.","year":"2014","journal-title":"Heidelberg"},{"key":"atypb19","first-page":"675","author":"Kantor E.","year":"2015","journal-title":"Berlin"},{"key":"atypb20","unstructured":"V. G. Kopytoff,\n                      Shifting online, Netflix faces new competition\n                      . New York Times (Business Day, Technology), September 26, 2010."},{"key":"atypb21","first-page":"586","author":"Korupolu M. R.","year":"1999","journal-title":"Philadelphia"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/90.879344"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/49.391753"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/MMCS.1994.292456"},{"key":"atypb25","first-page":"181","author":"Papadimitriou C.","year":"1995","journal-title":"Berlin"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0140-3664(95)98543-E"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"F. Schaffa and J.P. Nussbaumer,\n                      On bandwidth and storage tradeoffs in multimedia distribution networks\n                      , in IEEE INFOCOM, IEEE Computer Society, Los Alamitos, CA, 1995, pp. 1020-1026.","DOI":"10.1109\/INFCOM.1995.515978"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012730702524"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1103014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:53Z","timestamp":1787320733000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1103014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1103014"],"URL":"https:\/\/doi.org\/10.1137\/16m1103014","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}