For best experience please turn on javascript and use a modern browser!

Speaker: Neil Olver (CWI and VU Amsterdam)

Detail Summary
Date 6 March 2019
Time 16:00 - 16:45
Location Science Park 107


Rounding, matroids and matrices


Convex relaxations play a central role in our geometric and algorithmic understanding of NP-hard problems in combinatorial optimization. A standard template for constructing provably good algorithms is to take a fractional solution to the convex relaxation (which represents, in an incomplete way, a convex combination of actual solutions), and then find a good way of rounding it (either deterministically or randomly) to an actual integral solution.

I will discuss various aspects of modern rounding schemes, especially in the context of matroid constraints, and when aiming to control the spectral norm of certain matrices associated with the optimization problem. This has close connections to a growing theory about concentration of measure for matrix-valued random variables.

As a recurring motivation for improving these techniques, I will discuss a beautiful open problem in graph theory: the "thin tree" conjecture of Goddyn, concerning the existence of spanning trees in a graph that are sparse across every cut.


KdVI meeting room, room F3.20

Science Park 107

Room Location: KdVI meeting room, Science Park 107, room F3.20

Science Park 107
1098 XG Amsterdam