Top

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 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, v1,···,vn, First Fit assigns the point vi to the first 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 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.

All are welcome.