On the Best Possible Competitive Ratio for Multislope Ski Rental.

Hiroshi Fujiwara Takuma Kitano Toshihiro Fujito

Published in: ISAAC (2011)

Keyphrases

competitive ratio
single machine
lower bound
average case
optimal strategy
online algorithms
processing times
convergence rate
scheduling problem
monte carlo sampling
upper bound
reward function
branch and bound
queue length
branch and bound algorithm
completion times
np hard