Online Algorithms

Online Algorithms

Online Linear Discrepancy

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.