5 citations · 8 across the 8 of their papers we have counts for
11 papers
Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
Richard Santiago, Ivan Sergeev, Rico Zenklusen
The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an -competitive algorithm for the Matroid Secretary Problem (M…
Advances on Strictly -Modular IPs
Martin Nägele, Christian Nöbel, Richard Santiago +1
There has been significant work recently on integer programs (IPs) with a constraint marix with bounded subdeterminants.…
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…
Congruency-Constrained TU Problems Beyond the Bimodular Case
Martin Nägele, Richard Santiago, Rico Zenklusen
A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important specia…
A Simple Optimal Contention Resolution Scheme for Uniform Matroids
Danish Kashaev, Richard Santiago
Contention resolution schemes (or CR schemes), introduced by Chekuri, Vondrak and Zenklusen, are a class of randomized rounding algorithms for converting a fractional solution to a…
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…
New Approximations and Hardness Results for Submodular Partitioning Problems
Richard Santiago
We consider the following class of submodular k-multiway partitioning problems: (Sub--MP) $\min \sum_{i=1}^k f(S_i): S_1 \uplus S_2 \uplus \cdots \uplus S_k = V \mbox{ and } S_i…
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…
Multivariate Submodular Optimization
Richard Santiago, F. Bruce Shepherd
Submodular functions have found a wealth of new applications in data science and machine learning models in recent years. This has been coupled with many algorithmic advances in th…