Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization

Yixin Chen, Ankur Nath, Chunli Peng +1

For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than $1/e$ require continuous ideas, such as queries to the…