Journal article
Lower bounds for randomized algorithms for online chain partitioning
C Mathieu, O Ohrimenko
Information Processing Letters | ELSEVIER SCIENCE BV | Published : 2012
Abstract
We prove that the randomized competitive ratio of online chain partitioning of posets equals the deterministic competitive ratio. © 2012 Elsevier B.V. All rights reserved.