{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T17:07:40Z","timestamp":1637687260887},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2001,9]]},"abstract":"We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema.<\/jats:p>","DOI":"10.1145\/502102.502107","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"1069-1090","source":"Crossref","is-referenced-by-count":206,"title":["A unified approach to approximating resource allocation and scheduling"],"prefix":"10.1145","volume":"48","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[{"name":"AT&T Shannon Lab, Florham Park, NJ, USA"}]},{"given":"Reuven","family":"Bar-Yehuda","sequence":"additional","affiliation":[{"name":"Technion, Isreal Institute of Technology, Haifa, Israel"}]},{"given":"Ari","family":"Freund","sequence":"additional","affiliation":[{"name":"Technion, Isreal Institute of Technology, Haifa, Israel"}]},{"given":"Joseph","family":"(Seffi) Naor","sequence":"additional","affiliation":[{"name":"Technion, Isreal Institute of Technology, Haifa, Israel"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY, USA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","volume-title":"Applied Optimization: Computational Methods in Decision-Making Economics and Finance","author":"AKCOGLU K."},{"key":"e_1_2_1_2_1","volume-title":"10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 31-40","author":"ALBERS S.","year":"1999"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799354138"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s004530010009","article-title":"One for the price of two: a unified approach for approximating covering problems","volume":"27","author":"BAR-YEHUDA R.","year":"2000","journal-title":"Algorithmica"},{"key":"e_1_2_1_7_1","first-page":"27","article-title":"A local-ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"BAR-YEHUDA R.","year":"1985","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_8_1","volume-title":"4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Number 2129 in Lecture Notes in Computer Science","author":"BAR-YEHUDA R."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/A:1009822211065","article-title":"Multi-phase algorithms for throughput maximization for real-time scheduling","volume":"4","author":"BERMAN P.","year":"2000","journal-title":"Journal of Combinatorial Optimization"},{"key":"e_1_2_1_10_1","volume-title":"9th Annual International Symposium on Algorithms and Computation (ISAAC). Number 1533 in Lecture Notes in Computer Science","author":"ERLEBACH T."},{"key":"e_1_2_1_11_1","first-page":"135","article-title":"Conversion of coloring algorithms into maximum weight independent set algorithms. In Satellite Workshops of the 27th International Colloquium on Automata; Languages; and Programming (ICALP)","author":"ERLEBACH T.","year":"2000","journal-title":"Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE)."},{"key":"e_1_2_1_12_1","unstructured":"GAREY M. AND JOHNSON D. 1979. Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman and Company.]] GAREY M. AND JOHNSON D. 1979. Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman and Company.]]"},{"key":"e_1_2_1_13_1","volume-title":"4th Annual European Symposium on Algorithms (ESA). Number 1136 in Lecture Notes in Computer Science","author":"GERGOV J."},{"key":"e_1_2_1_14_1","volume-title":"10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 907-908","author":"GERGOV J.","year":"1999"},{"key":"e_1_2_1_15_1","unstructured":"GERGOV J. 2001. Personal communication.]] GERGOV J. 2001. Personal communication.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"GOLUMBIC M. 1980. Algorithmic graph theory and perfect graphs. Academic Press.]] GOLUMBIC M. 1980. Algorithmic graph theory and perfect graphs. Academic Press.]]","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"e_1_2_1_17_1","unstructured":"KHANNA S. 1999. Personal communication.]] KHANNA S. 1999. Personal communication.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0012-365X(91)90011-P","article-title":"A polynomial time approximation algorithm for dynamic storage allocation","volume":"88","author":"KIERSTEAD H. A.","year":"1991","journal-title":"Discrete Mathematics"},{"key":"e_1_2_1_19_1","volume-title":"20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Number 1974 in Lecture Notes in Computer Science","author":"LEONARDI S."},{"key":"e_1_2_1_20_1","unstructured":"PHILLIPS C. 2001. Personal communication.]] PHILLIPS C. 2001. Personal communication.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1002\/1099-1425(200011\/12)3:6<365::AID-JOS56>3.0.CO;2-P","article-title":"Off-line admission control for general scheduling problems","volume":"3","author":"PHILLIPS C.","year":"2000","journal-title":"Journal of Scheduling"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","article-title":"On the approximability of an interval scheduling problem","volume":"2","author":"SPIEKSMA F. C.","year":"1999","journal-title":"Journal of Scheduling"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255801"},{"key":"e_1_2_1_24_1","volume-title":"Workshop on Approximation Algorithms for Hard Problems in Combinatorial Optimization, The Fields Institute for Research in Mathematical Sciences.]]","author":"VAZIRANI V.","year":"1999"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/502102.502107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T10:04:57Z","timestamp":1614852297000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,9]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2001,9]]}},"alternative-id":["10.1145\/502102.502107"],"URL":"http:\/\/dx.doi.org\/10.1145\/502102.502107","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2001,9]]}}}