9 citations · 17 across the 6 of their papers we have counts for
6 papers · 1 filter
Sensitivity Analysis of the Maximum Matching Problem
Yuichi Yoshida, Samson Zhou
We consider the sensitivity of algorithms for the maximum matching problem against edge and vertex modifications. Algorithms with low sensitivity are desirable because they are rob…
Fast Fourier Sparsity Testing
Grigory Yaroslavtsev, Samson Zhou
A function is -sparse if it has at most non-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over $…
"Bring Your Own Greedy"+Max: Near-Optimal -Approximations for Submodular Knapsack
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Samson Zhou
The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to re…
Approximate -Sketching of Valuation Functions
Grigory Yaroslavtsev, Samson Zhou
We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function …
Adversarially Robust Submodular Maximization under Knapsack Constraints
Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev +1
We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed…
Optimal Parametric Search for Path and Tree Partitioning
Greg N. Frederickson, Samson Zhou
We present linear-time algorithms for partitioning a path or a tree with weights on the vertices by removing edges to maximize the minimum-weight component. We also use the sam…