AN IMPROVED BOUND FOR FIRST-FIT ON POSETS WITHOUT TWO LONG INCOMPARABLE CHAINS
Vida Dujmović, Gwenaël Joret, David, R. Wood · 2013
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 width w then Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992–1999, 2010) proved an upper bound of ckw2 on the number of chains used by First-Fit for some constant c, while Joret and Milans (Order, 28(3):455–464, 2011) gave one of ck2w. In this paper we prove an upper bound of the form ckw. This is best possible up to the value of c. 1.