Rightsizing Clusters for Time-Limited Tasks
Venkatesan T. Chakaravarthy, Padmanabha V. Seshadri, et al.
CLOUD 2021
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, Padmanabha V. Seshadri, et al.
CLOUD 2021
Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, et al.
Theory of Computing Systems
Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, et al.
Discrete Optimization
Anamitra R. Choudhury, Syamantak Das, et al.
SODA 2015