4 papers · 1 filter
A Decomposition Approach to the Weighted -server Problem
Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma
A natural variant of the classical online -server problem is the Weighted -server problem, where the cost of moving a server is its weight times the distance through which it…
On Minimizing Generalized Makespan on Unrelated Machines
Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
We consider the Generalized Makespan Problem (GMP) on unrelated machines, where we are given jobs and machines and each job has arbitrary processing time on ma…
Near-optimal Algorithms for Stochastic Online Bin Packing
Nikhil Ayyadevara, Rajni Dabas, Arindam Khan +1
We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the mi…
The Randomized Competitive Ratio of Weighted -server is at least Exponential
Nikhil Ayyadevara, Ashish Chiplunkar
The weighted -server problem is a natural generalization of the -server problem in which the cost incurred in moving a server is the distance traveled times the weight of the…