Bounding The Power Of Preemption In Randomized Scheduling. Canetti, R. & Irani, S. Proceedings of the 27th ACM Symposium on Theory of Computing, 27(4):993--1015, August, 1998.
Bounding The Power Of Preemption In Randomized Scheduling [link]Paper  abstract   bibtex   
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...
@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}
}
Downloads: 0