Rejecting jobs to minimize load and maximum flow-time

- A novel rejection model proposed for online job scheduling where online algorithm may reject ϵ-fraction of requests.
- We consider the restricted assignment setting where each job can be assigned only to a subset of machines.
- O(log2⁡1/ϵ)-competitive algorithm presented for minimizing the maximum load on any machine.
- O(1/ϵ4)-competitive algorithm presented for the problem of minimizing the maximum weighted flow-time.
- Above result can be extended for the objective of minimizing the maximum stretch.

The notion of competitive ratio often turns out to be too pessimistic for the analysis of online algorithms. Although the approach of resource augmentation (introduced by Kalyanasundaram and Pruhs) has been very successful in dealing with a variety of objective functions, there are problems for which even a (arbitrary) constant speedup cannot lead to a constant competitive algorithm. Here we propose a rejection model which permits the online algorithm to not serve epsilon-fraction of requests. We present O(log2⁡1/ε) and O(1/ε4)-competitive algorithms for the problems of load balancing and minimizing maximum flow time in the restricted assignment setting.