[theory students] talk on stable marriage problem (etc.) tomorrow

[Eric Bach <bach@xxxxxxxxxxx>]

Apologies if you have already seen this, but the topic
looks like it would be of interest to CS theory people.
Eric

-------------------------------------------------------------------------

From: 'JOSE RODRIGUEZ' via mathaas <mathaas@xxxxxxxxxxxxxxxxx>:

Tomorrow Yuri Faenza from Columbia University is giving a talk at theÂISyE
Colloquium.ÂHere is the talk info:

Stable matchings: lattices, polytypes, and applications - College of
Engineering - University of Wisconsin-Madison

April 15 @ 12:00 PM â 1:00 PM Central US TIme
Room 1163 ME

Abstract: In the classical matching model by Gale and Shapley, agents from
one side of the market (such as students/workers/doctors/â) have a strict
ordering of the agents from the other side of the market
(schools/firms/hospitals/â), and vice-versa. However, strict orders cannot
model many preference patterns that arise in problems such as
diversification of school cohorts, formation of teams, etc. Hence, much
attention has recently been reserved to matching problems where preferences
of agents have a more complex behavior, which can be described via certain
choice functions. In this talk, we investigate algorithmic properties of
these models, showing that the classical combinatorial approach based on the
lattice of stable matchings and the description of the convex hull of stable
matchings as an LP are intimately related. This approach may turn out to be
of interest for other problems in discrete optimization as well.ÂIf time
allows, I will also discuss some applications of stable matchings in choice
function models to affirmative action policies in New York City public high
schools.Â

Bio: Yuri Faenza is an associate professor in the IEOR department at
Columbia University. He works in discrete optimization, operations research,
matching theory, and their applications. His research has been funded by the
NSF (including an NSF Career award), the ONR, and the Swiss NSF.

-Jose