research
∙
03/01/2023
Scarf's algorithm and stable marriages
Scarf's algorithm gives a pivoting procedure to find a special vertex – ...
share
research
∙
03/01/2023
The Total Matching Polytope of Complete Bipartite Graphs
The total matching polytope generalizes the stable set polytope and the ...
research
∙
11/30/2022
Internal Closedness and von Neumann-Morgenstern Stability in Matching Theory: Structures and Complexity
Let G be a graph and suppose we are given, for each v ∈ V(G), a strict o...
research
∙
10/06/2022
The Power of Greedy for Online Minimum Cost Matching on the Line
We consider the online minimum cost matching problem on the line, in whi...
research
∙
03/01/2022
Discovering Opportunities in New York City's Discovery Program: an Analysis of Affirmative Action Mechanisms
Discovery program (DISC) is an affirmative action policy used by the New...
research
∙
06/24/2021
Slack matrices, k-products, and 2-level polytopes
In this paper, we study algorithmic questions concerning products of mat...
research
∙
11/13/2020
Affinely representable lattices, stable matchings, and choice functions
Birkhoff's representation theorem (Birkhoff, 1937) defines a bijection b...
research
∙
09/15/2020
Approximation Algorithms for The Generalized Incremental Knapsack Problem
We introduce and study a discrete multi-period extension of the classica...
research
∙
04/22/2020
Impact of Bias on School Admissions and Targeted Interventions
There is an inherent problem in the way students are evaluated - be it s...
research
∙
02/06/2020
Recognizing Cartesian products of matrices and polytopes
The 1-product of matrices S_1 ∈R^m_1 × n_1 and S_2 ∈R^m_2 × n_2 is the m...
research
∙
06/11/2019
Reinforcement Learning for Integer Programming: Learning to Cut
Integer programming (IP) is a general optimization framework widely appl...
research
∙
04/11/2019
Quasi-popular Matchings, Optimality, and Extended Formulations
Let G = (A ∪ B,E) be an instance of the stable marriage problem where ev...
research
∙
11/20/2018
Extended formulations from communication protocols in output-efficient time
Deterministic protocols are well-known tools to obtain extended formulat...
research
∙
11/16/2018
Understanding popular matchings via stable matchings
Let G = (A ∪ B, E) be an instance of the stable marriage problem with st...
research
∙
11/16/2018
Popularity, stability, and the dominant matching polytope
Let G = (A ∪ B, E) be an instance of the stable marriage problem with st...
research
∙
09/23/2018
Legal Assignments and fast EADAM with consent via classical theory of stable matchings
Gale and Shapley's college admission problem and concept of stability (G...
research
∙
07/06/2018
Limits of Treewidth-based tractability in Optimization
Sparse structures are frequently sought when pursuing tractability in op...
research
∙
05/26/2018
Popular Matchings and Limits to Tractability
We consider popular matching problems in both bipartite and non-bipartit...
research
∙
03/05/2018
Two-sided popular matchings in bipartite graphs with forbidden/forced elements and weights
Two-sided popular matchings in bipartite graphs are a well-known general...
research
∙
01/26/2018