Beating Greedy Asymptotically for Weighted k-Matroid Intersection

Abstract: Greedy is one of the most widely used algorithmic paradigms, both in practice and in theory. Its success is classically explained by matroid theory: whenever the underlying optimization problem has a matroid structure, Greedy is optimal.

Greedy also extends to problems involving multiple matroids, but its performance guarantee deteriorates to 1/k, where k is the number of matroids. For Weighted k-Matroid Intersection, Greedy has long been the asymptotically best-known algorithm. In this talk, I will survey recent progress that improves on Greedy for Weighted k-Matroid Intersection and related problems. The talk is aimed to be self-contained to introduce the main algorithm behind these improvements while presenting the necessary background. I will leave enough to discuss a few open problems that I am interested in.

This talk features works with:

– Euiwoong Lee (U. Mich), and Ola Svensson (EPFL).

– Neta Singer (EPFL).

– Neil Olver (LSE) and Neta Singer (EPFL).

Posted on Mar 17, 2026 in ACGO, Seminars