410 citations · 838 across the 10 of their papers we have counts for
4 papers · 1 filter
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…
Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint
Jing Tang, Xueyan Tang, Andrew Lim +3
Monotone submodular maximization with a knapsack constraint is NP-hard. Various approximation algorithms have been devised to address this optimization problem. In this paper, we r…
Approximation Algorithms for Probabilistic Graphs
Kai Han
We study the k-median and k-center problems in probabilistic graphs. We analyze the hardness of these problems, and propose several algorithms with improved approximation ratios co…
Cost-Effective Seed Selection in Online Social Networks
Kai Han, Yuntian He, Xiaokui Xiao +3
We study the min-cost seed selection problem in online social networks, where the goal is to select a set of seed nodes with the minimum total cost such that the expected number of…