{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T06:32:38Z","timestamp":1790231558357,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We study on-line scheduling in overloaded systems. Requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served. Still, we want to serve the \"best\" set of requests according to some criterion. In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios.<\/jats:p>\n                  <jats:p>We show that, surprisingly, in many other scenarios this is not the case. In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms. Our bound applies to several recently studied problems. In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, nonpreemptive algorithms.<\/jats:p>","DOI":"10.1137\/s0097539795283292","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"993-1015","source":"Crossref","is-referenced-by-count":46,"title":["Bounding the Power of Preemption in Randomized Scheduling"],"prefix":"10.1137","volume":"27","author":[{"given":"Ran","family":"Canetti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandy","family":"Irani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"J. Aspens, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts,\n                      On\u2010line load balancing with applications to machine scheduling and virtual circuit routing\n                      , in Proc. 25th ACM Symposium on the Theory of Computing, 1993, pp. 623\u2013631.","DOI":"10.1145\/167088.167248"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and S. Plotkin,\n                      Throughput\u2010competitive online routing\n                      , in 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 32\u201340.","DOI":"10.1109\/SFCS.1993.366884"},{"key":"R3","unstructured":"B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosen,\n                      Competitive non\u2010preemptive call control\n                      , in Proc. 5th ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 1994, pp. 312\u2013320."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani,\n                      On\u2010line admission control and circuit routing for high performance computing and communication\n                      , in Proc. 35th Annual IEEE Symposium on the Foundations of Computer Science, 1994, pp. 412\u2013423.","DOI":"10.1109\/SFCS.1994.365675"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Z. Broder, A. R. Karlin,\n                      Online load balancing\n                      , in Proc. 33rd Annual IEEE Symposium on the Foundations of Computer Science, 1992, pp. 218\u2013225.","DOI":"10.1109\/SFCS.1992.267770"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.0799"},{"key":"R7","unstructured":"Yossi Azar, Joseph Naor, Raphael Rom, The competitiveness of on\u2010line assignments, ACM, New York, 1992, 203\u20132101173894"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Bar\u2010Noy, R. Canetti, S. Kutten, Y. Mansour, and B. Schieber,\n                      Bandwidth allocation with preemption\n                      , in Proc. 27th ACM Symposium on Theory of Computing, 1995, pp. 616\u2013625.","DOI":"10.1145\/225058.225279"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1074"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"S. Baruah, G. Koren, B. Mishra, A. Raghunathan, L. Rosier, and D. Shasha,\n                      On\u2010line scheduling in the presence of overload\n                      , in Proc. 32nd Annual IEEE Symposium on the Foundations of Computer Science, 1991, pp. 100\u2013110.","DOI":"10.1109\/SFCS.1991.185354"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. A. Garay and I. S. Gopal,\n                      Call preemption in communication networks\n                      , in Proceedings of INFOCOM \u201892, IEEE, 1992.","DOI":"10.1109\/INFCOM.1992.263457"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0821"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Harchol\u2010Balter and A. B. Downey,\n                      Exploiting Process Lifetime Distributions for Dynamic Load Balancing\n                      , Tech. Report TR\u201095\u2010021, International Computer Science Institute, Berkeley, CA, 1995.","DOI":"10.1145\/224056.225838"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0019"},{"key":"R17","unstructured":"G. Koren and D. Shasha,\n                      Dover: An Optimal On\u2010Line Scheduling Algorithm for Overloaded Real\u2010Time Systems\n                      , Tech. Report 594, Courant Institute, New York University, 1992."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90165-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"S. Phillips and J. Westbrook,\n                      On\u2010line load balancing and network flow\n                      , in Proc. 25th ACM Symposium on Theory of Computing, 1993, pp. 402\u2013411.","DOI":"10.1145\/167088.167201"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"K. K. Ramakrishnan, L. Vaitzblit, C. Gray, U. Vahalia, D Ting, P. Tzelnic, S. Glaser, and W. Duso,\n                      Operating system support for a video\u2010on\u2010demand file service\n                      , in Network and Operating System Support for Digital Audio and Video: Fourth International Workshop, Springer\u2010Verlag, Lancaster, UK, 1993, pp. 225\u2013236.","DOI":"10.1007\/3-540-58404-8_20"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793248317"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90150-3"},{"key":"R24","unstructured":"Special Issue on Asynchronous Transfer Mode\n                      , Internat. J. Digital Analog Cabled Systems, 1 (4), 1988."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795283292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:02Z","timestamp":1787335922000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795283292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795283292"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795283292","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}