C&O Reading Group - Niv Buchbinder
Title: Chasing Positive Bodies
Speaker: | Niv Buchbinder |
Affiliation: | Tel Aviv University |
Location: | MC 5417 |
Abstract: We study the problem of chasing positive bodies in \ell_1: given a sequence of bodies K_t\subset R^n revealed online, where each K_t is defined by a mixed packing-covering linear program, the goal is to (approximately) maintain a point x_t \in K_t such that \sum_t \|x_t - x_{t-1}\|_1 is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching.