@article{canetti_bounding_1998,
	series = {{SIAM} {Journal} on {Computing}},
	title = {Bounding {The} {Power} {Of} {Preemption} {In} {Randomized} {Scheduling}},
	volume = {27},
	url = {http://citeseer.ist.psu.edu/160767.html},
	abstract = {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. 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.
Key words. randomized algorithms, scheduli...},
	number = {4},
	urldate = {2009-04-09TZ},
	journal = {Proceedings of the 27th ACM Symposium on Theory of Computing},
	author = {Canetti, Ran and Irani, Sandy},
	month = aug,
	year = {1998},
	keywords = {Ran Canetti,Sandy Irani Bounding The Power Of Preemption In, Randomized Scheduling,},
	pages = {993--1015}
}

{"_id":"kFihFhXeuEnnJtm2o","bibbaseid":"canetti-irani-boundingthepowerofpreemptioninrandomizedscheduling-1998","downloads":0,"creationDate":"2016-12-19T20:50:58.840Z","title":"Bounding The Power Of Preemption In Randomized Scheduling","author_short":["Canetti, R.","Irani, S."],"year":1998,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","series":"SIAM Journal on Computing","title":"Bounding The Power Of Preemption In Randomized Scheduling","volume":"27","url":"http://citeseer.ist.psu.edu/160767.html","abstract":"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. 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. Key words. randomized algorithms, scheduli...","number":"4","urldate":"2009-04-09TZ","journal":"Proceedings of the 27th ACM Symposium on Theory of Computing","author":[{"propositions":[],"lastnames":["Canetti"],"firstnames":["Ran"],"suffixes":[]},{"propositions":[],"lastnames":["Irani"],"firstnames":["Sandy"],"suffixes":[]}],"month":"August","year":"1998","keywords":"Ran Canetti,Sandy Irani Bounding The Power Of Preemption In, Randomized Scheduling,","pages":"993--1015","bibtex":"@article{canetti_bounding_1998,\n\tseries = {{SIAM} {Journal} on {Computing}},\n\ttitle = {Bounding {The} {Power} {Of} {Preemption} {In} {Randomized} {Scheduling}},\n\tvolume = {27},\n\turl = {http://citeseer.ist.psu.edu/160767.html},\n\tabstract = {We study on-line scheduling in overloaded systems.\nRequests for jobs arrive one by one as time proceeds; the\nserving agents have limited capacity and not all requests\ncan be served. Still, we want to serve the \"best\" set of\nrequests according to some criterion. In this situation, the\nability to preempt (i.e., abort) jobs in service in order to\nmake room for better jobs that would otherwise be rejected\nhas proven to be of great help in some scenarios. We show\nthat, surprisingly, in many other scenarios this is not the\ncase. In a simple, generic model, we prove a polylogarithmic\nlower bound on the competitiveness of randomized and\npreemptive on-line scheduling algorithms. Our bound applies\nto several recently studied problems. In fact, in certain\nscenarios our bound is quite close to the competitiveness\nachieved by known deterministic, nonpreemptive algorithms.\nKey words. randomized algorithms, scheduli...},\n\tnumber = {4},\n\turldate = {2009-04-09TZ},\n\tjournal = {Proceedings of the 27th ACM Symposium on Theory of Computing},\n\tauthor = {Canetti, Ran and Irani, Sandy},\n\tmonth = aug,\n\tyear = {1998},\n\tkeywords = {Ran Canetti,Sandy Irani Bounding The Power Of Preemption In, Randomized Scheduling,},\n\tpages = {993--1015}\n}\n\n","author_short":["Canetti, R.","Irani, S."],"key":"canetti_bounding_1998","id":"canetti_bounding_1998","bibbaseid":"canetti-irani-boundingthepowerofpreemptioninrandomizedscheduling-1998","role":"author","urls":{"Paper":"http://citeseer.ist.psu.edu/160767.html"},"keyword":["Ran Canetti","Sandy Irani Bounding The Power Of Preemption In","Randomized Scheduling",""],"downloads":0,"html":""},"search_terms":["bounding","power","preemption","randomized","scheduling","canetti","irani"],"keywords":["ran canetti","sandy irani bounding the power of preemption in","randomized scheduling",""],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}