# Combinatorics Seminar

Efficiency of First Fit Chain Partitioning Finite Posets

Date: 11/16/2017

Time: 3:30PM-4:30PM

Place: 315 Armstrong Hall

Michael Wigal

Abstract: Given a ﬁnite 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, v1,···,vn, First Fit assigns the point vi to the ﬁrst available chain in the chain partition of the points v1,···,vi−1. It is a known fact that First Fit has unbounded performance over the family of ﬁnite posets of width 2. We give a complete characterization of the family of ﬁnite posets in which First Fit performs with subexponential eﬃciency in terms of width. We will also review what is currently known on the family of posets in which First Fit performs with polynomial eﬃciency in terms of width. Joint work with Kevin Milans.

All are welcome.