{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T19:55:09Z","timestamp":1773086109829,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,6,21]],"date-time":"2023-06-21T00:00:00Z","timestamp":1687305600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,21]],"date-time":"2023-06-21T00:00:00Z","timestamp":1687305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1007\/s10951-023-00786-6","type":"journal-article","created":{"date-parts":[[2023,6,21]],"date-time":"2023-06-21T22:03:52Z","timestamp":1687385032000},"page":"103-118","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The preemptive resource allocation problem"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7737-1200","authenticated-orcid":false,"given":"Kanthi","family":"Sarpatwar","sequence":"first","affiliation":[]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,21]]},"reference":[{"issue":"2","key":"786_CR1","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/jos.74","volume":"5","author":"M Adler","year":"2002","unstructured":"Adler, M., Gibbons, P. B., & Matias, Y. (2002). Scheduling space-sharing for internet advertising. Journal of Scheduling, 5(2), 103\u2013119.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"786_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A. A., & Sviridenko, M. (2004). Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8(3), 307\u2013328.","journal-title":"Journal of Combinatorial Optimization"},{"key":"786_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Eli\u00e1\u0161, M., & Khan, A. (2016). Improved approximation for vector bin packing. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms (pp. 1561\u20131579).","DOI":"10.1137\/1.9781611974331.ch106"},{"issue":"4","key":"786_CR4","doi-asserted-by":"publisher","first-page":"1256","DOI":"10.1137\/080736831","volume":"39","author":"N Bansal","year":"2009","unstructured":"Bansal, N., Caprara, A., & Sviridenko, M. (2009). A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4), 1256\u20131278.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"786_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2532645","volume":"10","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., & Salavatipour, M. R. (2014). A logarithmic approximation for unsplittable flow on line graphs. ACM Transactions on Algorithms, 10(1), 1.","journal-title":"ACM Transactions on Algorithms"},{"issue":"5","key":"786_CR6","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., & Schieber, B. (2001). A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48(5), 1069\u20131090.","journal-title":"Journal of the ACM"},{"issue":"2","key":"786_CR7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Guha, S., Naor, J., & Schieber, B. (2001). Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing, 31(2), 331\u2013352.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"786_CR8","doi-asserted-by":"publisher","first-page":"48:1","DOI":"10.1145\/2000807.2000816","volume":"7","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, G., Chakrabarti, A., Karloff, H. J., & Rabani, Y. (2011). An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms, 7(4), 48:1-48:7.","journal-title":"ACM Transactions on Algorithms"},{"key":"786_CR9","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V. T., Choudhury, A. R., Gupta, S., Roy, S., & Sabharwal, Y. (2014). Improved algorithms for resource allocation under varying capacity. In European symposium on algorithms (pp. 222\u2013234).","DOI":"10.1007\/978-3-662-44777-2_19"},{"issue":"4","key":"786_CR10","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., & Khanna, S. (2004). On multidimensional packing problems. SIAM Journal on Computing, 33(4), 837\u2013851.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"786_CR11","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1080\/07408170208928886","volume":"34","author":"B Chen","year":"2002","unstructured":"Chen, B., Hassin, R., & Tzur, M. (2002). Allocation of bandwidth and storage. IIE Transactions, 34(5), 501\u2013507.","journal-title":"IIE Transactions"},{"key":"786_CR12","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., & Codenotti, P. (2009). Resource minimization job scheduling. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques (pp. 70\u201383).","DOI":"10.1007\/978-3-642-03685-9_6"},{"key":"786_CR13","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Guha, S., Khanna, S., & Naor, J. (2004). Machine minimization for scheduling jobs with interval constraints. In Proceedings of the 45th symposium on foundations of computer science (FOCS 2004), 17\u201319 October 2004, Rome, Italy (pp. 81\u201390).","DOI":"10.1109\/FOCS.2004.38"},{"issue":"4","key":"786_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1023\/A:1024060710627","volume":"6","author":"M Dawande","year":"2003","unstructured":"Dawande, M., Kumar, S., & Sriskandarajah, C. (2003). Performance bounds of algorithms for scheduling advertisements on a web page. Journal of Scheduling, 6(4), 373\u2013394.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"786_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10951-005-5217-6","volume":"8","author":"M Dawande","year":"2005","unstructured":"Dawande, M., Kumar, S., & Sriskandarajah, C. (2005). Scheduling web advertisements: A note on the MINSPACE problem. Journal of Scheduling, 8(1), 97\u2013106.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"786_CR16","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1287\/moor.1110.0499","volume":"36","author":"L Fleischer","year":"2011","unstructured":"Fleischer, L., Goemans, M. X., Mirrokni, V. S., & Sviridenko, M. (2011). Tight approximation algorithms for maximum separable assignment problems. Mathematical Operations Research, 36(3), 416\u2013431.","journal-title":"Mathematical Operations Research"},{"key":"786_CR17","doi-asserted-by":"crossref","unstructured":"Fox, K., & Korupolu, M. (2013). Weighted flowtime on capacitated machines. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms (pp. 129\u2013143).","DOI":"10.1137\/1.9781611973105.10"},{"issue":"5","key":"786_CR18","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1023\/B:JOSH.0000036860.90818.5f","volume":"7","author":"A Freund","year":"2004","unstructured":"Freund, A., & Naor, J. (2004). Approximating the advertisement placement problem. Journal of Scheduling, 7(5), 365\u2013374.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"786_CR19","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"AM Frieze","year":"1984","unstructured":"Frieze, A. M., & Clarke, M. R. B. (1984). Approximation algorithms for the m-dimensional 0\u20131 knapsack problem: Worst-case and probabilistic analyses. European Journal of Operational Research, 15(1), 100\u2013109.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"786_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/2742343","volume":"2","author":"N Jain","year":"2015","unstructured":"Jain, N., Menache, I., Naor, J., & Yaniv, J. (2015). Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters. ACM Transactions on Parallel Computing, 2(1), 3.","journal-title":"ACM Transactions on Parallel Computing"},{"key":"786_CR21","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/3-540-47867-1_24","volume":"47","author":"K Jansen","year":"2002","unstructured":"Jansen, K., & Porkolab, L. (2002). On preemptive resource constrained scheduling: Polynomial-time approximation schemes. Integer Programming and Combinatorial Optimization, 47, 329\u2013349.","journal-title":"Integer Programming and Combinatorial Optimization"},{"issue":"1","key":"786_CR22","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jagm.2000.1128","volume":"38","author":"B Kalyanasundaram","year":"2001","unstructured":"Kalyanasundaram, B., & Pruhs, K. (2001). Eliminating migration in multi-processor scheduling. Journal of Algorithms, 38(1), 2\u201324.","journal-title":"Journal of Algorithms"},{"key":"786_CR23","first-page":"1","volume":"9","author":"A Kaul","year":"2017","unstructured":"Kaul, A., Aggarwal, S., Gupta, A., Dayama, N., Krishnamoorthy, M., & Jha, P. C. (2017). Optimal advertising on a two-dimensional web banner. International Journal of System Assurance Engineering and Management, 9, 1\u20136.","journal-title":"International Journal of System Assurance Engineering and Management"},{"issue":"11","key":"786_CR24","doi-asserted-by":"publisher","first-page":"1571","DOI":"10.1109\/TKDE.2007.190640","volume":"19","author":"S Kumar","year":"2007","unstructured":"Kumar, S., Dawande, M., & Mookerjee, V. (2007). Optimal scheduling and placement of internet banner advertisements. IEEE Transactions on Knowledge and Data Engineering, 19(11), 1571\u20131584.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"1","key":"786_CR25","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02248588","volume":"26","author":"EL Lawler","year":"1990","unstructured":"Lawler, E. L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26(1), 125\u2013133.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"786_CR26","first-page":"148","volume":"141","author":"C McDiarmid","year":"1989","unstructured":"McDiarmid, C. (1989). On the method of bounded differences. Surveys in Combinatorics, 141(1), 148\u2013188.","journal-title":"Surveys in Combinatorics"},{"issue":"3","key":"786_CR27","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1287\/inte.2017.0886","volume":"47","author":"S Pandey","year":"2017","unstructured":"Pandey, S., Dutta, G., & Joshi, H. (2017). Survey on revenue management in media and broadcasting. Interfaces, 47(3), 195\u2013213.","journal-title":"Interfaces"},{"key":"786_CR28","doi-asserted-by":"crossref","unstructured":"Phillips, C. A., Uma, R. N., & Wein, J. (2000). Off-line admission control for general scheduling problems. In Proceedings of the eleventh annual ACM-SIAM symposium on discrete algorithms (pp. 879\u2013888).","DOI":"10.1002\/1099-1425(200011\/12)3:6<365::AID-JOS56>3.0.CO;2-P"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00786-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-023-00786-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00786-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,11]],"date-time":"2024-02-11T13:12:50Z","timestamp":1707657170000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-023-00786-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,21]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["786"],"URL":"https:\/\/doi.org\/10.1007\/s10951-023-00786-6","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,21]]},"assertion":[{"value":"17 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}