Journal article

Lower bounds for randomized algorithms for online chain partitioning

C Mathieu, O Ohrimenko

Information Processing Letters | 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.