BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/3279/11-March-2010-CWI-DIAMANT-Seminar-Combinator
ics-and-Optimization-Dov-Samet
DTSTAMP:20100307T000000
SUMMARY:CWI-DIAMANT Seminar Combinatorics and Opti
mization, Dov Samet
ATTENDEE;ROLE=Speaker:Dov Samet
DTSTART;VALUE=DATE:20100311
DTEND;VALUE=DATE:20100311
LOCATION:Amsterdam, CWI, L017
DESCRIPTION:The core of a marriage problem consist
s of its stable matchings. When men and women are
objectively ranked in a marriage problem, say by b
eauty, then the core is a singleton: pairing indiv
iduals of equal rank is the only stable matching.
We generalize this observation using natural metri
cs on rankings and on matchings, as well as a meas
ure of the gap in rank between mates in a matching
. We provide bounds on the diameter of the core, a
nd on the rank gap of stable matchings in terms of
the diameters of the sets of rankings, and conclu
de that when the set of rankings is small, so are
the core and the rank gap in stable matchings. We
also show that when the rank gap in stable matchin
gs is small, then the core is also small. For mor
e information, see http://homepages.cwi.nl/~moniqu
e/acoseminar/.
X-ALT-DESC;FMTTYPE=text/html:\n The core
of a marriage problem consists of its stable\n
matchings. When men and women are objectively
ranked in a\n marriage problem, say by bea
uty, then the core is a singleton:\n pairin
g individuals of equal rank is the only stable\n
matching. We generalize this observation usi
ng natural metrics\n on rankings and on mat
chings, as well as a measure of the gap\n i
n rank between mates in a matching. We provide bou
nds on the\n diameter of the core, and on t
he rank gap of stable matchings\n in terms
of the diameters of the sets of rankings, and\n
conclude that when the set of rankings is sma
ll, so are the\n core and the rank gap in s
table matchings. We also show that\n when t
he rank gap in stable matchings is small, then the
core\n is also small.

\n \n \
n For more information, see http://homepages.cwi.nl/~monique/acosemin
ar/.

\n \n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/3279/11-March-2010-CWI-DIAMANT-Seminar-Combinator
ics-and-Optimization-Dov-Samet
END:VEVENT
END:VCALENDAR