BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Near-optimal Adaptive Policies for Dynamic Matching Markets
DTSTART:20260330T111500
DTEND:20260330T120000
DTSTAMP:20260528T130628Z
UID:d05e94d6692cae17f66d7af9ea68bb9a0c8e56ab9e8a0c3d1c917504
CATEGORIES:Conferences - Seminars
DESCRIPTION:Alireza Amanihamedani\, PhD candidate in Operations Research a
 t London Business School\, United Kingdom \nAbstract:\nWe study a continu
 ous-time\, infinite-horizon dynamic bipartite matching problem. Suppliers 
 arrive according to a Poisson process\; while waiting\, they may abandon t
 he queue at a uniform rate. Customers on the other hand must be matched up
 on arrival. The objective is to minimize the expected long-term average co
 st subject to a throughput constraint on the total match rate. \n\nPrevio
 us literature on dynamic matching focuses on "static" policies\, where the
  matching decisions do not depend explicitly on the state of the supplier 
 queues\, achieving constant-factor approximations. By contrast\, we design
  "adaptive" policies\, which leverage queue length information\, and obtai
 n near-optimal polynomial-time algorithms for several classes of instances
 .\n\nFirst\, we develop a bi-criteria fully polynomial-time approximation 
 scheme for dynamic matching on networks with a constant number of queues--
 that computes a (1-ε)-approximation of the optimal policy in time polynom
 ial in both the input size and 1/ε.  A key new technique is a hybrid LP 
 relaxation\, which combines static and state-dependent LP approximations o
 f the queue dynamics\, after a decomposition of the network. Networks with
  a constant number of queues are motivated by deceased organ donation sche
 mes\, where the supply types can be divided according to blood and tissue 
 types. \n\nThe above algorithm\, combined with a careful spatial decompos
 ition gives an efficient polynomial-time approximation scheme for dynamic 
 matching on Euclidean networks of fixed dimension. The Euclidean case is o
 f interest in ride-hailing and spatial service platforms\, where the goal 
 is to fulfill as many trips as possible while minimizing driving distances
 .\n\nBiography:\nAlireza Amanihamedani is a final-year PhD candidate in Op
 erations Research at London Business School\, advised by Prof. Ali Aouad. 
 His research interests are in online and dynamic optimization with applica
 tions to market design. Alireza’s research has been supported by the Goo
 gle PhD fellowship in algorithms and optimization (2025).
LOCATION:ME C2 405 https://plan.epfl.ch/?room==ME%20C2%20405
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR