MATH Seminar

Title: First-Fit is Linear on $(r+s)$-free Posets
Seminar: Combinatorics
Speaker: Kevin Milans of The University of South Carolina
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2011-10-21 at 4:00PM
Venue: W306
Download Flyer
Abstract: 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.