{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T21:26:52Z","timestamp":1790026012219,"version":"4.0.1"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF","award":["96-00402, 99-00217"],"award-info":[{"award-number":["96-00402, 99-00217"]}]},{"name":"EU","award":["14084 (APPOL)"],"award-info":[{"award-number":["14084 (APPOL)"]}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["DAAH04-96-1-0181"],"award-info":[{"award-number":["DAAH04-96-1-0181"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Science","award":["9480198"],"award-info":[{"award-number":["9480198"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["386\/99"],"award-info":[{"award-number":["386\/99"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-99817"],"award-info":[{"award-number":["CCR-99817"]}],"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":[[2011,9]]},"abstract":"<jats:p>\n            We study the problem of finding a most profitable subset of\n            <jats:italic>n<\/jats:italic>\n            given tasks, each with a given start and finish time as well as profit and resource requirement, that at no time exceeds the quantity\n            <jats:italic>B<\/jats:italic>\n            of available resource. We show that this NP-hard Resource Allocation problem can be (1\/2 \u2212 \u03b5)-approximated in randomized polynomial time, which improves upon earlier approximation results.\n          <\/jats:p>","DOI":"10.1145\/2000807.2000816","type":"journal-article","created":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T14:02:19Z","timestamp":1317132139000},"page":"1-7","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["An improved approximation algorithm for resource allocation"],"prefix":"10.1145","volume":"7","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[{"name":"Illinois Institute of Technology, Chicago, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Chakrabarti","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, NH"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs\u2013Research, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[{"name":"The Hebrew University of Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of IPCO. 401--414","author":"Calinescu G.","unstructured":"Calinescu , G. , Chakrabarti , A. , Karloff , H. J. , and Rabani , Y . 2002. Improved approximation algorithms for resource allocation . In Proceedings of IPCO. 401--414 . Calinescu, G., Chakrabarti, A., Karloff, H. J., and Rabani, Y. 2002. Improved approximation algorithms for resource allocation. In Proceedings of IPCO. 401--414."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408170208928886"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90385-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Leonardi S. Marchetti-Spaccamela A. and \n      Vitaletti A\n  . \n  2000\n  . Approximation algorithms for bandwidth and storage allocation problems under real time constraints. In Proceedings of FSTTCS Lecture Notes in Computer Science Series vol. \n  1974\n  . \n  Springer 409--420.   Leonardi S. Marchetti-Spaccamela A. and Vitaletti A. 2000. Approximation algorithms for bandwidth and storage allocation problems under real time constraints. In Proceedings of FSTTCS Lecture Notes in Computer Science Series vol. 1974. Springer 409--420.","DOI":"10.1007\/3-540-44450-5_33"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.2.338"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1425(200011\/12)3:6<365::AID-JOS56>3.0.CO;2-P"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000816","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2000807.2000816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:03Z","timestamp":1750244403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2000807.2000816"],"URL":"https:\/\/doi.org\/10.1145\/2000807.2000816","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2004-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}