BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:684@lincs.fr
DTSTART;TZID=Europe/Paris:20220126T150000
DTEND;TZID=Europe/Paris:20220126T160000
DTSTAMP:20220202T093612Z
URL:https://www.lincs.fr/events/a-stochastic-matching-between-graph-theory
 -and-linear-algebra/
SUMMARY:A stochastic matching between graph theory and linear algebra
DESCRIPTION:Stochastic dynamic matching has numerous applications\, ranging
 from&nbsp\;supply-chain management to kidney exchange programs. In a
 matching&nbsp\;problem\, different classes arrive according to independent
 Poisson&nbsp\;processes. Unmatched items are stored in a queue\, and two
 items can be&nbsp\;matched if their classes are neighbors in a (simple)
 compatibility&nbsp\;graph. We analyze the efficiency of matching policies
 in terms of&nbsp\;system stability and of matching rates between different
 classes. Our&nbsp\;results\, which rely on the observation of the
 conservation equation&nbsp\;between departures and arrivals\, are
 threefold. We first relate the&nbsp\;way the conservation equation maps
 arrival and departure vectors\, the&nbsp\;structure of the compatibility
 graph\, and the existence of a stable&nbsp\;policy. This allows us to
 derive a necessary and sufficient stability&nbsp\;condition that is
 verifiable in polynomial time. Secondly\, we describe&nbsp\;the convex
 polytope of non-negative solutions of the conservation&nbsp\;equation. When
 this polytope is reduced to a single point\, we give a&nbsp\;closed-form
 expression of the solution\; in general\, we characterize&nbsp\;the
 vertices of this polytope using again the graph structure.
 Lastly\,&nbsp\;we show that greedy policies cannot\, in general\, achieve
 every point&nbsp\;in the polytope. In contrast\, non-greedy policies can at
 least reach&nbsp\;any point of the interior of this polytope\, and can also
 reach its&nbsp\;boundary if a specific condition on its vertices is
 checked.\n&nbsp\;\nThis is a joint work with Céline Comte and Ana Bušic.
CATEGORIES:Seminars,Youtube
LOCATION:Zoom + LINCS\, 23 avenue d'Italie\, Paris\, 75013\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23 avenue d'Italie\,
 Paris\, 75013\, France;X-APPLE-RADIUS=100;X-TITLE=Zoom + LINCS:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20211031T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR