Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid
|Affiliation:||University of Waterloo|
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.
200 University Avenue West
Waterloo, ON N2L 3G1