- Series
- ACO Student Seminar
- Time
- Friday, September 28, 2018 - 1:15pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Michael Wigal – Math, Georgia Tech – wigal@gatech.edu – http://people.math.gatech.edu/~mwigal3/
- Organizer
- He Guo

Given a finite partially ordered set (poset) of width $w$, Dilworth's theorem gives an existence and minimality of a chain partition of size $w$. First-Fit is an online algorithm for creating a chain partition of a poset. Given a linear ordering of the points of the poset, $v_1, \cdots, v_n$, First-Fit assigns the point $v_i$ to the first available chain in the chain partition of the points $v_1, \cdots, v_{i-1}$. It is a known fact that First-Fit has unbounded performance over the family of finite posets of width 2. We give a complete characterization of the family of finite posets in which First-Fit performs with subexponential efficiency in terms of width. We will also review what is currently known on the family of posets in which First-Fit performs with polynomial efficiency in terms of width. Joint work with Kevin Milans.