3 papers
cs.DS2021
Efficient and Effective Algorithms for Revenue Maximization in Social Advertising
Kai Han, Benwei Wu, Jing Tang +3
We consider the revenue maximization problem in social advertising, where a social network platform owner needs to select seed users for a group of advertisers, each with a payment…
cs.DS2021
The Power of Randomization: Efficient and Effective Algorithms for Constrained Submodular Maximization
Kai Han, Shuang Cui, Tianshuai Zhu +3
Submodular optimization has numerous applications such as crowdsourcing and viral marketing. In this paper, we study the fundamental problem of non-negative submodular function max…
cs.DS2020
Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time
Kai Han, Zongmai Cao, Shuang Cui +1
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…