16 citations · 77 across the 28 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Alina Ene, Huy L. Nguyen
We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint. Our main contribution is an algorithm that achieves a nearly-optimal, $1 - 1/…
cs.LG2017★ 15 cited
Decomposable Submodular Function Minimization: Discrete and Continuous
Alina Ene, Huy L. Nguyen, László A. Végh
This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the…