{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:53:45Z","timestamp":1725576825837},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642183171"},{"type":"electronic","value":"9783642183188"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-18318-8_15","type":"book-chapter","created":{"date-parts":[[2011,1,24]],"date-time":"2011-01-24T08:58:06Z","timestamp":1295859486000},"page":"166-177","source":"Crossref","is-referenced-by-count":2,"title":["A 3\/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Karrenbauer","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"15_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"C.L. Liu","year":"1973","unstructured":"Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM\u00a020(1), 46\u201361 (1973)","journal-title":"J. ACM"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Buttazzo, G.: Hard Real-time Computing Systems: Predictable Scheduling Algorithms And Applications (Real-Time Systems Series) (2004)","DOI":"10.1007\/0-387-27578-9"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Yao, A.C.C.: Resource constrained scheduling as generalized bin packing. J. Combin. Theory Ser. A\u00a021, 257\u2013298 (1976)","journal-title":"J. Combin. Theory Ser. A"},{"key":"15_CR4","unstructured":"Johnson, D.S.: Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA (1973)"},{"issue":"4","key":"15_CR5","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1\u2009+\u2009\u03b5 in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"15_CR6","first-page":"312","volume-title":"FOCS 1982","author":"N. Karmarkar","year":"1982","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: FOCS 1982, pp. 312\u2013320. IEEE, Los Alamitos (1982)"},{"key":"15_CR7","volume-title":"Algorithm Design for Computer System Design","author":"E.G. Coffman Jr.","year":"1984","unstructured":"Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin-packing\u2014an updated survey. In: Algorithm Design for Computer System Design. Springer, Heidelberg (1984)"},{"issue":"12","key":"15_CR8","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.1109\/12.477248","volume":"44","author":"J. Liebeherr","year":"1995","unstructured":"Liebeherr, J., Burchard, A., Oh, Y., Son, S.H.: New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. Comput.\u00a044(12), 1429\u20131442 (1995)","journal-title":"IEEE Trans. Comput."},{"key":"15_CR9","volume-title":"Real-Time Systems","author":"J. Liu","year":"2000","unstructured":"Liu, J.: Real-Time Systems. Prentice Hall PTR, Upper Saddle River (2000)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Bini, E., Buttazzo, G., Buttazzo, G.: A hyperbolic bound for the rate monotonic algorithm. In: ECRTS 2001, p. 59 (2001)","DOI":"10.1109\/EMRTS.2001.934000"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Rothvo\u00df, T.: Static-priority Real-time Scheduling: Response Time Computation is NP-hard. In: RTSS (2008)","DOI":"10.1109\/RTSS.2008.25"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Audsley, A.N., Burns, A., Richardson, M., Tindell, K.: Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 284\u2013292 (1993)","DOI":"10.1049\/sej.1993.0034"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Fisher, N., Baruah, S.: A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines. In: ECRTS 2005, pp. 117\u2013126 (2005)","DOI":"10.1109\/ECRTS.2005.1"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Baruah, S.K., Pruhs, K.: Open problems in real-time scheduling. Journal of Scheduling (2009)","DOI":"10.1007\/s10951-009-0137-5"},{"key":"15_CR15","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"J. Leung","year":"2004","unstructured":"Leung, J.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Inc., Boca Raton (2004)"},{"issue":"1","key":"15_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1287\/opre.26.1.127","volume":"26","author":"S.K. Dhall","year":"1978","unstructured":"Dhall, S.K., Liu, C.L.: On a real-time scheduling problem. Operations Research\u00a026(1), 127\u2013140 (1978)","journal-title":"Operations Research"},{"key":"15_CR17","volume-title":"Handbook of Scheduling \u2014 Algorithms, Models, and Performance Analysis","author":"S.K. Dhall","year":"2004","unstructured":"Dhall, S.K.: Approximation algorithms for scheduling time-critical jobs on multiprocessor systems. In: Leung, J.Y.T. (ed.) Handbook of Scheduling \u2014 Algorithms, Models, and Performance Analysis. Chapman & Hall\/CRC, Boca Raton (2004)"},{"issue":"3","key":"15_CR18","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF01088806","volume":"9","author":"Y. Oh","year":"1995","unstructured":"Oh, Y., Son, S.H.: Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Syst.\u00a09(3), 207\u2013239 (1995)","journal-title":"Real-Time Syst."},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/978-3-642-04128-0_39","volume-title":"Algorithms - ESA 2009","author":"A. Karrenbauer","year":"2009","unstructured":"Karrenbauer, A., Rothvo\u00df, T.: An average-case analysis for rate-monotonic multiprocessor real-time scheduling. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 432\u2013443. Springer, Heidelberg (2009)"},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-70575-8_21","volume-title":"Automata, Languages and Programming","author":"F. Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Rothvo\u00df, T.: A PTAS for static priority real-time scheduling with resource augmentation. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 246\u2013257. Springer, Heidelberg (2008)"},{"key":"15_CR21","unstructured":"Baruah, S., Goossens, J.: Scheduling real-time tasks: Algorithms and complexity. In: Handbook of Scheduling \u2014 Algorithms, Models, and Performance Analysis (2004)"},{"key":"15_CR22","unstructured":"Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: SODA 1990 (1990)"},{"key":"15_CR23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033142","volume-title":"Combinatorial Optimization","author":"W.J. Cook","year":"1997","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. John Wiley, New York (1997)"},{"key":"15_CR24","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18318-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T23:46:19Z","timestamp":1637192779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18318-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642183171","9783642183188"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18318-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}