Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, et al.
IPDPS 2013
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(log21/ε) and O(1/ε4)-competitive algorithms for the problems of load balancing and minimizing maximum flow time in the restricted assignment setting.
Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, et al.
IPDPS 2013
Saurabh Goyal, Anamitra R. Choudhury, et al.
ICML 2020
Subendhu Rongali, Anamitra R. Choudhury, et al.
ISGT ASIA 2015
Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, et al.
Theory of Computing Systems