With Noah Streib and William T. Trotter, I have devised an online algorithm for linear discrepancy that is optimal. For general posets (and interval orders) of linear discrepancy k, it guarantees a linear extension with linear discrepancy at most 3k-1. For semiorders of linear discrepancy k, it guarantees a linear extension with linear discrepancy at most 2k. Full details can be found in our paper Online Linear Discrepancy for Partially Ordered Sets, which appears in An Irregular Mind (Szemerédi is 70), volume 21 of the Bolyai Society Mathematical Studies. The slides from my talk at the 2010 SIAM Conference on Discrete Mathematics (DM10) are also available.
Research