40 citations · 242 across the 33 of their papers we have counts for
20 papers · 1 filter
Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases
Chandra Chekuri, Lars Rohwedder, Neta Singer +2
Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function over m…
Universal set families for maximization of nonnegative submodular and XOS functions
Chandra Chekuri, Richard Ueltzen, Jan Vondrak
We consider the question of designing a universal family of sets such that for any function in a certain class, we have $$\max_{S \in…
Faster Submodular Maximization for Several Classes of Matroids
Monika Henzinger, Paul Liu, Jan Vondrak +1
The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often w…
Cardinality constrained submodular maximization for random streams
Paul Liu, Aviad Rubinstein, Jan Vondrak +1
We consider the problem of maximizing submodular functions in single-pass streaming and secretaries-with-shortlists models, both with random arrival order. For cardinality constrai…
A polynomial lower bound on adaptive complexity of submodular maximization
Wenzheng Li, Paul Liu, Jan Vondrak
In large-data applications, it is desirable to design algorithms with a high degree of parallelization. In the context of submodular optimization, adaptive complexity has become a…
Stability and Recovery for Independence Systems
Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrak
Two genres of heuristics that are frequently reported to perform much better on "real-world" instances than in the worst case are greedy algorithms and local search algorithms. In…