A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem.
Marek ChrobakLawrence L. LarmoreCarsten LundNick ReingoldPublished in: Inf. Process. Lett. (1997)
Keyphrases
- competitive ratio
- lower bound
- randomized algorithm
- upper bound
- single machine
- average case
- online algorithms
- optimal strategy
- branch and bound
- branch and bound algorithm
- processing times
- optimal solution
- convergence rate
- objective function
- lower and upper bounds
- worst case
- np hard
- scheduling problem
- sample complexity
- learning algorithm
- single server
- search algorithm