It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size κ. In particular, if P has width w, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992-1999], proved an upper bound of ckw 2 on the number of chains used by First-Fit for some constant c, while Joret and Milans [Order, 28 (2011), pp. 455-464] gave one of ck 2w. In this paper we prove an upper bound of the form ckw. This is most possible up to the value of c.

Additional Metadata
Keywords First-Fit, On-line chain partition
Persistent URL dx.doi.org/10.1137/110855806
Journal SIAM Journal on Discrete Mathematics
Citation
Dujmović, V, Joret, G. (Gwenaël), & Wood, D. (2012). An improved bound for First-Fit on posets without two long incomparable chains. SIAM Journal on Discrete Mathematics, 26(3), 1068–1075. doi:10.1137/110855806