Combinatorial Optimization Reading Group - Benjamin Moore

Friday, November 15, 2019 1:00 pm - 1:00 pm EST (GMT -05:00)

Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid

Speaker: Ben Moore
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

In 1978, it was shown that a natural greedy algorithm gives a 1/2 approximation to submodular maximization subject to a matroid constraint. In 2019, Niv Buchbinder, Moran Feldman, and Mohit Garg gave the first deterministic improvement over the 1/2 approximation, giving a 0.5008-approximation. I will present this result.