16 citations · 77 across the 28 of their papers we have counts for
4 papers · 1 filter
A Parallel Double Greedy Algorithm for Submodular Maximization
Alina Ene, Huy L. Nguyen, Adrian Vladu
We study parallel algorithms for the problem of maximizing a non-negative submodular function. Our main result is an algorithm that achieves a nearly-optimal approximation…
Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
Alina Ene, Huy L. Nguyen
We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is…
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, Adrian Vladu
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of…
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
Alina Ene, Huy L. Nguyen
In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constr…