Georgia Institute of Technology College of Sciences

First-Fit is an online algorithm that partitions the elements of a poset into chains. When presented with a new element x, First-Fit adds x to the first chain whose elements are all comparable to x. In 2004, Pemmaraju, Raman, and Varadarajan introduced the Column Construction Method to prove that when P is an interval order of width w, First-Fit partitions P into at most 10w chains. This bound was subsequently improved to 8w by Brightwell, Kierstead, and Trotter, and independently by Narayanaswamy and Babu. The poset r+s is the disjoint union of a chain of size r and a chain of size s. A poset is an interval order if and only if it does not contain 2+2 as an induced subposet. Bosek, Krawczyk, and Szczypka proved that if P is an (r+r)-free poset of width w, then First-Fit partitions P into at most 3rw^2 chains and asked whether the bound can be improved from O(w^2) to O(w). We answer this question in the affirmative. By generalizing the Column Construction Method, we show that if P is an (r+s)-free poset of width w, then First-Fit partitions P into at most 8(r-1)(s-1)w chains. This is joint work with Gwena\"el Joret.