{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:06Z","timestamp":1759638606053,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-9896232CCR-0113192","CCR-0093117CCR-9820965CCR-0113192CCR-9820965"],"award-info":[{"award-number":["CCR-9896232CCR-0113192","CCR-0093117CCR-9820965CCR-0113192CCR-9820965"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,10]]},"abstract":"\n We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of\n M<\/jats:italic>\n multimedia objects (data objects) that need to be assigned to a storage system consisting of\n N<\/jats:italic>\n disks\n d<\/jats:italic>\n 1<\/jats:sub>\n ,\n d<\/jats:italic>\n 2<\/jats:sub>\n \u2026,\n \n d\n N<\/jats:sub>\n <\/jats:italic>\n . We are also given sets\n U<\/jats:italic>\n 1<\/jats:sub>\n ,\n U<\/jats:italic>\n 2<\/jats:sub>\n ,\u2026,\n \n U\n M<\/jats:sub>\n <\/jats:italic>\n such that\n \n U\n i<\/jats:sub>\n <\/jats:italic>\n is the set of clients seeking the\n i<\/jats:italic>\n th data object. Each disk\n \n d\n j<\/jats:sub>\n <\/jats:italic>\n is characterized by two parameters, namely, its\n storage capacity<\/jats:italic>\n \n C\n j<\/jats:sub>\n <\/jats:italic>\n which indicates the maximum number of data objects that may be assigned to it, and a\n load capacity<\/jats:italic>\n \n L\n j<\/jats:sub>\n <\/jats:italic>\n which indicates the maximum number of clients that it can serve. The goal is to find a placement of data objects to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.\n <\/jats:p>\n \n We study this data placement problem for two natural classes of storage systems, namely,\n homogeneous<\/jats:italic>\n and\n uniform ratio<\/jats:italic>\n . We show that an algorithm developed by Shachnai and Tamir [2000a] for data placement achieves the\n best possible<\/jats:italic>\n absolute bound regarding the number of clients that can always be satisfied. We also show how to implement the algorithm so that it has a running time of\n O<\/jats:italic>\n ((\n N<\/jats:italic>\n +\n M<\/jats:italic>\n ) log(\n N<\/jats:italic>\n +\n M<\/jats:italic>\n )). In addition, we design a polynomial-time approximation scheme, solving an open problem posed in the same paper.\n <\/jats:p>","DOI":"10.1145\/1597036.1597037","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximation algorithms for data placement on parallel disks"],"prefix":"10.1145","volume":"5","author":[{"given":"Leana","family":"Golubchik","sequence":"first","affiliation":[{"name":"University of Southern California, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramakrishna","family":"Thurimella","sequence":"additional","affiliation":[{"name":"University of Denver, CO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"An","family":"Zhu","sequence":"additional","affiliation":[{"name":"Google Inc., Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191852"},{"volume-title":"Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms. 185--194","author":"Chekuri C.","key":"e_1_2_1_2_1","unstructured":"Chekuri , C. , and Khanna , S . 1999. On multidimensional packing problems . In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms. 185--194 . Chekuri, C., and Khanna, S. 1999. On multidimensional packing problems. In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms. 185--194."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015776903524"},{"key":"e_1_2_1_5_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company. Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"e_1_2_1_7_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco."},{"volume-title":"Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). 265--276","author":"Kashyap S.","key":"e_1_2_1_8_1","unstructured":"Kashyap , S. , and Khuller , S . 2003. Algorithms for non-uniform size data placement on parallel disks . In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). 265--276 . Kashyap, S., and Khuller, S. 2003. Algorithms for non-uniform size data placement on parallel disks. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). 265--276."},{"volume-title":"The Art of Computer Programming","author":"Knuth D. E.","key":"e_1_2_1_9_1","unstructured":"Knuth , D. E. 1973. The Art of Computer Programming , vol. 3 . Addison-Wesley . Knuth, D. E. 1973. The Art of Computer Programming, vol. 3. Addison-Wesley."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010057"},{"volume-title":"Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249","author":"Shachnai H.","key":"e_1_2_1_13_1","unstructured":"Shachnai , H. , and Tamir , T . 2000b. Polynomial time approximation schemes for class-constrained packing problems . In Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249 . Shachnai, H., and Tamir, T. 2000b. Polynomial time approximation schemes for class-constrained packing problems. In Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249."},{"volume-title":"Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249","author":"Shachnai H.","key":"e_1_2_1_14_1","unstructured":"Shachnai , H. , and Tamir , T . 2003. Approximation schemes for generalized 2-dimensional vector packing with application to data placement . In Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249 . Shachnai, H., and Tamir, T. 2003. Approximation schemes for generalized 2-dimensional vector packing with application to data placement. In Proceedings of the Workshop on Approximation Algorithms (APPROX). 238--249."},{"key":"e_1_2_1_15_1","first-page":"4","article-title":"A case for shared nothing","volume":"9","author":"Stonebraker M.","year":"1986","unstructured":"Stonebraker , M. 1986 . A case for shared nothing . Datab. Engin. 9 , 1, 4 -- 9 . Stonebraker, M. 1986. A case for shared nothing. Datab. Engin. 9, 1, 4--9.","journal-title":"Datab. Engin."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/223587.223605"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597037","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1597036.1597037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:10Z","timestamp":1750249090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1597036.1597037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1597036.1597037"],"URL":"https:\/\/doi.org\/10.1145\/1597036.1597037","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2006-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}