5 papers
The Dirichlet Mechanism for rounding with strong negative correlation, with applications
David G. Harris, George Z. Li, Nitya Raju +1
Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" , where the goal is to select exactly one edge for each r…
Robust Stable Matchings: Dealing with Changes in Preferences
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley [GS62]. Given two instances and on the same set…
Dimension-Free Correlated Sampling for the Hypersimplex
Joseph, Naor, Nitya Raju +4
Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability sim…
Stable Matching: Dealing with Changes in Preferences
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
We study stable matchings that are robust to preference changes in the two-sided stable matching setting of Gale and Shapley[GS62]. Given two instances and on the same set…
A Structural and Algorithmic Study of Stable Matching Lattices of "Nearby" Instances, with Applications
Rohith Reddy Gangam, Tung Mai, Nitya Raju +1
Recently MV18 identified and initiated work on the new problem of understanding structural relationships between the lattices of solutions of two "nearby" instances of stable match…