Title: An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
Abstract: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 $k$. In particular, if $P$ has ...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 $k$. 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^{2}w$. In this paper we prove an upper bound of the form $ckw$. This is most possible up to the value of $c$.Read More