27 citations · 32 across the 10 of their papers we have counts for
5 papers · 1 filter
Fixed-Parameter Tractable Submodular Maximization over a Matroid
Shamisa Nematollahi, Adrian Vladu, Junyao Zhao
In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank is treate…
Universal Online Contention Resolution with Preselected Order
Junyao Zhao
Online contention resolution scheme (OCRS) is a powerful technique for online decision making, which--in the case of matroids--given a matroid and a prior distribution of active el…
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond -Approximation
Aviad Rubinstein, Junyao Zhao
In this work we give two new algorithms that use similar techniques for (non-monotone) submodular function maximization subject to a cardinality constraint. The first is an offline…
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…
Budget-Smoothed Analysis for Submodular Maximization
Aviad Rubinstein, Junyao Zhao
The greedy algorithm for monotone submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a factor. A…