Fall 2017

LP Relaxations for Reordering Buffer Management

Thursday, Sep. 14, 2017 3:30 pm4:00 pm

Add to Calendar

We present LP relaxations for uniform and non-uniform reordering buffer management, and their application to the design and analysis of competitive online algorithms and polynomial time approximation algorithms for these problems. The talk is based on several joint papers with Noa Avigdor-Elgrabli, Sungjin Im, and Benjamin Moseley.

PDF icon 2017simonsbuffer.pdf960.89 KB