BIU theory seminar- May 10 : Roie Levin (TAU) - Chasing Positive Bodies

[Arnold Filtser]

Hello all,

Next week (Wed May 10, at 12) we will meet for our theory seminar.

Location: Building 605 room 14.

See you there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Roie Levin (TAU)

Title: Chasing Positive Bodies.
Abstract: We study the problem of chasing positive bodies in \ell_1: given a sequence of bodies K_t = {x \in R^n_+ | C^t x ≥ 1,P^t x ≤ 1} revealed online, where C^t and P^t are nonnegative matrices, 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.

We give an O(log d)-competitive algorithm for this problem, where d is the maximum row sparsity of any matrix Ct. This bypasses and improves exponentially over the lower bound of sqrt(n) known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless. We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.

This is joint work with Sayan Bhattacharya, Niv Buchbinder, and Thatchaphol Saranurak.

[Arnold Filtser]

Change of location: tomorrow, due to expected noise, the seminar will take place in building 504, room 1.

This is only a one time change, and next week our seminar will come back to building 605, room 14.

See you there at 12!