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.