Automatic taxonomy generation: Issues and possibilities
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
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. © 1998 Society for Industrial and Applied Mathematics.
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
Robert C. Durbeck
IEEE TACON
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking