{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T15:34:12Z","timestamp":1680449652118},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,1]]},"abstract":"\n The\n data migration<\/jats:italic>\n problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. We consider this problem with the objective of minimizing the sum of completion times of all storage devices. It is modeled by a transfer graph, where vertices represent the storage devices, and the edges indicate the data transfers required between pairs of devices. Each vertex has a nonnegative weight, and each edge has a release time and a processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (\n Journal of Algorithms, 55:42--57, 2005<\/jats:italic>\n ) gave a 9-approximation algorithm for the problem when edges have arbitrary processing times and are released at time zero. We improve Kim's result by giving a 5.06-approximation algorithm. We also address the\n open shop scheduling<\/jats:italic>\n problem,\n O<\/jats:italic>\n |\n \n r\n j<\/jats:sub>\n <\/jats:italic>\n | \u2211\n \n w\n j<\/jats:sub>\n C\n j<\/jats:sub>\n <\/jats:italic>\n , and show that it is a special case of the data migration problem. Queyranne and Sviridenko (\n Journal of Scheduling, 5:287-305, 2002<\/jats:italic>\n ) gave a 5.83-approximation algorithm for the nonpreemptive version of the open shop problem. They state as an obvious open question whether there exists an algorithm for open shop scheduling that gives a performance guarantee better than 5.83. Our 5.06 algorithm for data migration proves the existence of such an algorithm. Crucial to our improved result is a property of the linear programming relaxation for the problem. Similar linear programs have been used for various other scheduling problems. Our technique may be useful in obtaining improved results for these problems as well.\n <\/jats:p>","DOI":"10.1145\/1125994.1126001","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"116-129","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Improved results for data migration and open shop scheduling"],"prefix":"10.1145","volume":"2","author":[{"given":"Rajiv","family":"Gandhi","sequence":"first","affiliation":[{"name":"Rutgers University, Camden, New Jersey"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[{"name":"University of Iceland, Reykjavik, Iceland"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University, Camden, New Jersey"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[{"name":"The Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2006,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Workshop on Algorithm Engineering. Springer-Verlag","author":"Anderson E."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2677"},{"key":"e_1_2_1_3_1","volume-title":"Scheduling Algorithms","author":"Brucker P."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming. Springer-Verlag","author":"Chakrabarti S."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327180"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214054"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Cook W. J. Cunningham W. H. Pulleyblank W. R. and Schrijver A. 1998. Combinatorial Optimization. J Wiley New York.]] Cook W. J. Cunningham W. H. Pulleyblank W. R. and Schrijver A. 1998. Combinatorial Optimization. J Wiley New York.]]","DOI":"10.1002\/9781118033142"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211009"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Hall J."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789945.2789946"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1031-8"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 6th International Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag","author":"Hoogeveen H."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970342585X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.009"},{"key":"e_1_2_1_16_1","volume-title":"Logistics of Production and Recovery. S. C. Graves, et al., Eds, 445--522.]]","author":"Lawler E. L.","year":"1993"},{"key":"e_1_2_1_17_1","unstructured":"Marx D. 2004. Complexity results for minimum sum edge coloring. http:\/\/www.cs.bme.hu\/~dmarx\/papers\/marx-sum-edge-hard.pdf.]] Marx D. 2004. Complexity results for minimum sum edge coloring. http:\/\/www.cs.bme.hu\/~dmarx\/papers\/marx-sum-edge-hard.pdf.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113607.3113905"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00251-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/jos.96"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Sanders P."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645587.659466"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702415007"},{"key":"e_1_2_1_24_1","volume-title":"Mixed integer programming formulations for production planning and scheduling problems. Invited talk at the Twelfth International Symposium on Mathematical Programming","author":"Wolsey L."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1125994.1126001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:33:18Z","timestamp":1672255998000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1125994.1126001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1145\/1125994.1126001"],"URL":"http:\/\/dx.doi.org\/10.1145\/1125994.1126001","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]},"assertion":[{"value":"2006-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}