Article ID Journal Published Year Pages File Type
427633 Information Processing Letters 2012 4 Pages PDF
Abstract

We prove that the randomized competitive ratio of online chain partitioning of posets equals the deterministic competitive ratio.

► We consider performance of randomized algorithms for online chain partitioning of posets. ► We construct a set of partial orders that are hard instances for randomized algorithms. ► We prove that known lower bounds for deterministic algorithms hold for randomized algorithms.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Lower bounds for randomized algorithms for online chain partitioning
Authors
, ,