Benwei Wu — accepted AI-conference papers

2021

Randomized Algorithms for Submodular Function Maximization with a $k$-System Constraint

Shuang Cui, Kai Han, Tianshuai Zhu, Jing Tang, Benwei Wu, He Huang

ICML 2021spotlight

Submodular optimization has numerous applications such as crowdsourcing and viral marketing. In this paper, we study the problem of non-negative submodular function maximization subject to a $k$-system constraint, which generalizes many other important constraints in submodular optimization such as…

Cited by 16 Source ↗PDF ↗Scholar ↗

2020

Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time

Kai Han, zongmai Cao, Shuang Cui, Benwei Wu

NeurIPS 2020poster

We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. The prior best-known deterministic approximation ratio for this problem is $\frac{1}{4}-\epsilon$ under $\mathcal{O}(({n^4}/{\epsilon})\log n)$ time complexity. We show that this dete…

Cited by 24 Source ↗PDF ↗Scholar ↗