A guessing game and randomized online algorithms
Steven S. Seiden · 2000
We present the first general framework for proving lower bounds for randomized online algorithms using the von Neumann/Yao principle.This framework encompasses and explains many existent lower bound results, and allows us to prove several new ones.The foremost of the new results is a lower bound of 1.58197 for the online TCP acknowledgment problem of Dooly, Goldman and Scott [11].Other new results include: a lower bound of 1.34880 for randomized online two-machine flow shop scheduling, a lower bound of 1.15775 for randomized online total completion time scheduling on parallel machines and a lower bound of 1.06532 for scheduling with machine cost.Out method provides a sort of 'Master theorem' for proving randomized lower bounds.