4 citations · 10 across the 14 of their papers we have counts for
4 papers · 1 filter
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic…
Beyond Worst-Case Budget-Feasible Mechanism Design
Aviad Rubinstein, Junyao Zhao
Motivated by large-market applications such as crowdsourcing, we revisit the problem of budget-feasible mechanism design under a "small-bidder assumption". Anari, Goel, and Nikzad…
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Binghui Peng, Aviad Rubinstein
Dynamic algorithms come in three main flavors: (insertions-only), (deletions-only), or (both inser…
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…