The Randomized Competitive Ratio of Weighted $k$-server is at least Exponential.

Nikhil Ayyadevara Ashish Chiplunkar

Published in: CoRR (2021)

Keyphrases

competitive ratio
randomized algorithm
single machine
lower bound
average case
optimal strategy
online algorithms
processing times
completion times
convergence rate
weighted sum
scheduling problem
reward function
multi agent
e learning
decision problems
single server
single machine scheduling problem