Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, November 18, 2025, 12:15 pm

Duration: 30 minutes

Location: OAT S15

Speaker: Theophile Thiery

Improved Approximation for Weighted k-Matroid Intersection

Matroid theory provides a unifying abstraction for many combinatorial optimization problems. By designing generic algorithms for the resulting matroid problems, we can address a wide range of concrete applications in engineering, operations research, and data science. In a landmark result from 1969, Edmonds gave an optimal algorithm for problems that can be cast as the intersection of two matroids, a result that continues to shape modern combinatorial optimization. However, as soon as three or more matroid constraints are involved, our understanding becomes limited, even in seemingly simple cases. In this talk, I will present an improved approximation algorithm for weighted k-Matroid Intersection and discuss some of the key techniques behind this result. I will also give a brief tour of multi-matroid problems to highlight current challenges and questions that drive my research. No prior knowledge of matroid theory is required.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login