{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:01:36Z","timestamp":1725487296906},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_86","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"1123-1137","source":"Crossref","is-referenced-by-count":1,"title":["Real-Time Scheduling with a Budget"],"prefix":"10.1007","author":[{"given":"Joseph Seffi","family":"Naor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"86_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"E.M. Arkin","year":"1987","unstructured":"E.M. Arkin and E.B. Sliverberg. \u201cScheduling jobs with fixed start and end times\u201d. Discrete Applied Math., 18:1\u20138, 1987.","journal-title":"Discrete Applied Math."},{"key":"86_CR2","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","volume":"2","author":"P. Baptiste","year":"1999","unstructured":"P. Baptiste. Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. J. of Scheduling, 2:245\u2013252, 1999.","journal-title":"J. of Scheduling"},{"key":"86_CR3","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"B.B.+.0.0._.A. Bar-Noy","year":"2001","unstructured":"[BB+00]_A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Schieber. A unified approach to approximating resource allocation and scheduling. J. of the ACM, 48:1069\u20131090, 2001.","journal-title":"J. of the ACM"},{"key":"86_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"B.G.+.9.9._.A. Bar-Noy","year":"2001","unstructured":"[BG+99]_A. Bar-Noy, S. Guha, J. Naor and B. Schieber Approximating the throughput of real-time multiple machine scheduling. SIAM J. on Computing, 31:331\u2013352, 2001.","journal-title":"SIAM J. on Computing"},{"key":"86_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P. Berman","year":"2000","unstructured":"P. Berman and B. DasGupta. \u201cMulti-phase algorithms for throughput maximization for real-time scheduling.\u201d J. of Combinatorial Optimization, 4:307\u2013323, 2000.","journal-title":"J. of Combinatorial Optimization"},{"key":"86_CR6","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, R. Ostrovsky, and Y. Rabani. \u201cApproximation algorithms for the job interval selection problem and related scheduling problems.\u201d FOCS, 2001.","DOI":"10.1109\/SFCS.2001.959909"},{"key":"86_CR7","unstructured":"M.R. Garey and D.S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, 1979."},{"key":"86_CR8","doi-asserted-by":"crossref","unstructured":"N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of FOCS, 1996.","DOI":"10.1109\/SFCS.1996.548489"},{"issue":"1","key":"86_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R. Hassin","year":"1992","unstructured":"R. Hassin, Approximation schemes for the restricted shortest path problem. In Mathematics of Operations Research, 17(1): 36\u201342, 1992.","journal-title":"Mathematics of Operations Research"},{"key":"86_CR10","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"V. Kann. Maximum bounded 3-dimensional matching is max SNP-complete. Information Processing Letters, 37:27\u201335, 1991.","journal-title":"Information Processing Letters"},{"key":"86_CR11","doi-asserted-by":"crossref","unstructured":"Y. Karuno and H. Nagamochi, A 2-approximation algorithm for the multivehicle scheduling problem on a path with release and handling times. ESA, 2001.","DOI":"10.1007\/3-540-44676-1_18"},{"issue":"1","key":"86_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"S. Khuller, A. Moss, J. Naor, The budgeted maximum coverage problem. Information Processing Letters 70(1): 39\u201345, 1999.","journal-title":"Information Processing Letters"},{"issue":"1","key":"86_CR13","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1109\/90.986559","volume":"10","author":"D. H. Lorenz","year":"2002","unstructured":"D. H. Lorenz and A. Orda, Optimal partition of QoS requirements on unicast paths and multicast trees, IEEE\/ACM Trans. on Networking, 10(1), 102\u2013114, 2002.","journal-title":"IEEE\/ACM Trans. on Networking"},{"key":"86_CR14","doi-asserted-by":"crossref","unstructured":"D. H. Lorenz, A. Orda, D. Raz, Y. Shavitt, Efficient QoS partition and routing of unicast and multicast, 8th Int. Workshop on Quality of Service, Pittsburgh, 2000.","DOI":"10.1109\/IWQOS.2000.847940"},{"key":"86_CR15","unstructured":"J. Naor, H. Shachnai and T. Tamir Real-time Scheduling with a Budget, http:\/\/www.cs.technion.ac.il\/~hadas\/PUB\/rtbudget.ps."},{"key":"86_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"F. C. R. Spieksma","year":"1999","unstructured":"F. C. R. Spieksma. \u201cOn the approximability of an interval scheduling problem.\u201d J. of Scheduling, 2:215\u2013227, 1999.","journal-title":"J. of Scheduling"},{"key":"86_CR17","unstructured":"M. Tennenholtz. Some tractable combinatorial auctions. AAAI\/IAAI, 98\u2013103, 2000."},{"key":"86_CR18","unstructured":"V. Vazirani, Approximation algorithms, Springer Verlag, 2001."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_86","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:13:40Z","timestamp":1556666020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_86","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}