Title:

Rounding, matroids and matrices

Abstract:

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.

Location:

KdVI meeting room, room F3.20