{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T18:29:02Z","timestamp":1790965742421,"version":"4.1.0"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We introduce the data placement problem to model this problem. We have a set of caches $\\mathcal{F}$, a set of clients $\\mathcal{D}$, and a set of data objects $\\mathcal{O}$. Each cache i can store at most $u_i$ data objects. Each client $j\\in\\mathcal{D}$ has demand $d_j$ for a specific data object $o(j)\\in\\mathcal{O}$ and has to be assigned to a cache that stores that object. Storing an object o in cache i incurs a storage cost of $f_i^o$, and assigning client j to cache i incurs an access cost of $d_jc_{ij}$. The goal is to find a placement of the data objects to caches respecting the capacity constraints, and an assignment of clients to caches so as to minimize the total storage and client access costs. We present a 10-approximation algorithm for this problem. Our algorithm is based on rounding an optimal solution to a natural linear-programming relaxation of the problem. One of the main technical challenges encountered during rounding is to preserve the cache capacities while incurring only a constant-factor increase in the solution cost. We also introduce the connected data placement problem to capture settings where write-requests are also issued for data objects, so that one requires a mechanism to maintain consistency of data. We model this by requiring that all caches containing a given object be connected by a Steiner tree to a root for that object, which issues a multicast message upon a write to (any copy of) that object. The total cost now includes the cost of these Steiner trees. We devise a 14-approximation algorithm for this problem. We show that our algorithms can be adapted to handle two variants of the problem: (a) a k-median variant, where there is a specified bound on the number of caches that may contain a given object, and (b) a generalization where objects have lengths and the total length of the objects stored in any cache must not exceed its capacity.<\/jats:p>","DOI":"10.1137\/080715421","type":"journal-article","created":{"date-parts":[[2008,8,28]],"date-time":"2008-08-28T02:21:45Z","timestamp":1219890105000},"page":"1411-1429","source":"Crossref","is-referenced-by-count":174,"title":["Approximation Algorithms for Data Placement Problems"],"prefix":"10.1137","volume":"38","author":[{"given":"Ivan","family":"Baev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,8,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Bartal, and A. Fiat,\n                      Heat & dump: Competitive distributed paging\n                      , in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, 1993, pp. 22\u201331.","DOI":"10.1109\/SFCS.1993.366885"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0924"},{"key":"R3","unstructured":"I. D. Baev and R. Rajaraman,\n                      Approximation algorithms for data placement in arbitrary networks\n                      , in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 661\u2013670."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, D. Coppersmith, and M. Sviridenko,\n                      Improved approximation algorithms for broadcast scheduling\n                      , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 344\u2013353.","DOI":"10.1145\/1109557.1109596"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1073"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. Byrka,\n                      An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem\n                      , in Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization, Springer, Berlin, 2007, pp. 29\u201343.","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0524-9"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/356876.356883"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko,\n                      Tight approximation algorithms for maximum general assignment problems\n                      , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 611\u2013620.","DOI":"10.1145\/1109557.1109624"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/75577.75583"},{"key":"R13","unstructured":"S. Guha and K. Munagala,\n                      Improved algorithms for the data placement problem\n                      , in Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 106\u2013107."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener,\n                      Provisioning a virtual private network: A network design problem for multicommodity flow\n                      , in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, pp. 389\u2013398.","DOI":"10.1145\/380752.380830"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Gupta, A. Kumar, and T. Roughgarden,\n                      Simple and better approximation algorithms for network design\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 365\u2013372.","DOI":"10.1145\/780542.780597"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Heddaya and S. Mirdad,\n                      WebWave: Globally load balanced fully distributed caching of hot published documents\n                      , in Proceedings of the 17th International Conference on Distributed Computing Systems, IEEE Computer Society, Washington, DC, 1997, pp. 160\u2013168.","DOI":"10.1109\/ICDCS.1997.597907"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Korupolu and M. Dahlin,\n                      Coordinated placement and replacement for large-scale distributed caches\n                      , in Proceedings of the IEEE Workshop on Internet Applications, 1999, pp. 62\u201371.","DOI":"10.1109\/WIAPP.1999.788018"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1129"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1100"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"C. Krick, H. R\u00e4cke, and M. Westermann,\n                      Approximation algorithms for data management in networks\n                      , in Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, 2001, pp. 237\u2013246.","DOI":"10.1145\/378580.378651"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/71.250099"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0178"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"R. Levi, D. Shmoys, and C. Swamy,\n                      LP-based approximation algorithms for capacitated facility location\n                      , in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3064, Springer, Berlin, 2004, pp. 206\u2013218.","DOI":"10.1007\/978-3-540-25960-2_16"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"J. H. Lin and J. S. Vitter,\n                      $\\epsilon$-approximations with minimum packing constraint violation\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"B. Maggs, F. Meyer auf der Heide, B. V\u00f6cking, and M. Westermann,\n                      Exploiting locality for data management in systems of limited bandwidth\n                      , in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 284\u2013293.","DOI":"10.1109\/SFCS.1997.646117"},{"key":"R28","unstructured":"F. Meyer auf der Heide, B. V\u00f6cking, and M. Westermann,\n                      Caching in networks\n                      , in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 430\u2013439."},{"key":"R29","unstructured":"A. Meyerson, K. Munagala, and S. Plotkin,\n                      Web caching using access statistics\n                      , in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 354\u2013363."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"M. P\u00e1l, \u00c9. Tardos, and T. Wexler,\n                      Facility location with nonuniform hard capacities\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 329\u2013338.","DOI":"10.1109\/SFCS.2001.959907"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"M. Rabinovich, I. Rabinovich, R. Rajaraman, and A. Aggarwal,\n                      A dynamic object replication and migration protocol for an Internet hosting service\n                      , in Proceedings of the IEEE International Conference on Distributed Computing Systems, 1999, pp. 101\u2013113.","DOI":"10.1109\/ICDCS.1999.776511"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"R. Ravi and F. S. Selman,\n                      Approximation algorithms for the traveling purchaser problem and its variants in network design\n                      , in Algorithms\u2014ESA '99, Lecture Notes in Comput. Sci. 1643, Springer, Berlin, 1999, pp. 29\u201340.","DOI":"10.1007\/3-540-48481-7_4"},{"key":"R33","unstructured":"R. Ravi and A. Sinha,\n                      Multicommodity facility location\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 335\u2013342."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys,\n                      Approximation algorithms for facility location problems\n                      , in Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Comput. Sci. 1913, Springer, Berlin, 2000, pp. 27\u201333.","DOI":"10.1007\/3-540-44436-X_4"},{"key":"R35","unstructured":"D. B. Shmoys, C. Swamy, and R. Levi,\n                      Facility location with service installation costs\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 1081\u20131090."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. I. Aardal,\n                      Approximation algorithms for facility location problems\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"R38","unstructured":"C. Swamy,\n                      Algorithms for Data Placement Problems\n                      , manuscript, 2004."},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1112-3"},{"key":"R40","unstructured":"C. Swamy and D. B. Shmoys,\n                      Fault-tolerant facility location\n                      , in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 735\u2013736."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/249978.249982"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"J. Zhang, B. Chen, and Y. Ye,\n                      A multi-exchange local search algorithm for the capacitated facility location problem\n                      , in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3064, Springer, Berlin, 2004, pp. 219\u2013233.","DOI":"10.1007\/978-3-540-25960-2_17"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080715421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:06Z","timestamp":1787336346000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080715421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/080715421"],"URL":"https:\/\/doi.org\/10.1137\/080715421","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}