5 papers
Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information
Richard Santiago, Ivan Sergeev, Rico Zenklusen
Random order online contention resolution schemes (ROCRS) are structured online rounding algorithms with numerous applications and links to other well-known online selection proble…
A Parameterized Family of Meta-Submodular Functions
Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd
Submodular function maximization has found a wealth of new applications in machine learning models during the past years. The related supermodular maximization models (submodular m…
Weakly Submodular Function Maximization Using Local Submodularity Ratio
Richard Santiago, Yuichi Yoshida
Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) f…
Beyond Submodular Maximization via One-Sided Smoothness
Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd
The multilinear framework has achieved the breakthrough approximation for maximizing a monotone submodular function subject to a matroid constraint. This framework has a co…
Multi-Agent Submodular Optimization
Richard Santiago, F. Bruce Shepherd
Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) , where is a given family of feasible…