research
∙
05/09/2023
Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
The Matroid Secretary Conjecture is a notorious open problem in online o...
share
research
∙
02/14/2023
Advances on Strictly Δ-Modular IPs
There has been significant work recently on integer programs (IPs) min{c...
research
∙
11/28/2022
Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information
Random order online contention resolution schemes (ROCRS) are structured...
research
∙
09/07/2021
Congruency-Constrained TU Problems Beyond the Bimodular Case
A long-standing open question in Integer Programming is whether integer ...
research
∙
05/25/2021
An Optimal Monotone Contention Resolution Scheme for Uniform and Partition Matroids
A common approach to solve a combinatorial optimization problem is to fi...
research
∙
06/25/2020
New Approximations and Hardness Results for Submodular Partitioning Problems
We consider the following class of submodular k-multiway partitioning pr...
research
∙
06/23/2020
A Parameterized Family of Meta-Submodular Functions
Submodular function maximization has found a wealth of new applications ...
research
∙
04/30/2020
Weakly Submodular Function Maximization Using Local Submodularity Ratio
Weak submodularity is a natural relaxation of the diminishing return pro...
research
∙
04/19/2019
Beyond Submodular Maximization
While there are well-developed tools for maximizing a submodular functio...
research
∙
03/10/2018
