ISE Seminar-Physical Flow Approximations for the FCFS Stochastic Matching Model

Speaker Professor Edward H. Kaplan, Yale School of Management
Date: 4/13/2017
Time: 4 p.m.

112 Transportation Building

Event Contact: Holly Kizer, Assistant Director of Graduate Studies

Industrial & Enterprise Systems Engineering

Event Type: Seminar/Symposium


The FCFS stochastic matching model, where each server in an infinite sequence is matched to the first customer from a second infinite sequence that is eligible to receive service from the server in question, developed from queueing problems addressed by Kaplan (1984) in the context of public housing assignments.  The main goal of this model is to determine the matching rates between eligible customer and server types, that is, what fraction of all matches occur between type-i customers and type-j servers.  This model was solved in a beautiful paper by Adan and Weiss (2012), but the resulting equation for the matching rates is quite complicated, involving the sum of terms over all permutations of the server types (Adan and Weiss suggest that their calculation might be of complexity #P).  Here we develop physical flow approximations for the matching rates that in some cases reduce to exact results, and via simulation are shown to be highly accurate.   As our approximations only require the solution of a system of linear equations along with the identification of a small number of terms, they provide a tractable alternative to the exact solution.  

(Note: this is joint work with Mohammad Fazel Zarandi, Yale School of Management) 



Edward H. Kaplan is the William N. and Marie A. Beach Professor of Operations Research, Public Health, and Engineering at Yale University’s School of Management. An expert in operations research, mathematical modeling and statistics, Kaplan was elected to the National Academy of Engineering and the Institute of Medicine (now the National Academy of Medicine). His research in HIV prevention and counterterrorism has been recognized with the Edelman Award, Lanchester Prize, Centers for Disease Control’s Charles C. Shepard Science Award, INFORMS President’s Award, three Koopman Prizes, and numerous other awards. Kaplan was the Lady Davis Visiting Professor of medicine and of statistics at the Hebrew University of Jerusalem, and also served as a visiting professor to the Faculty of Industrial Engineering and Management at the Technion-Israel Institute of Technology, the Survey Research Center at UC Berkeley, Columbia’s Graduate School of Business, MIT’s Sloan School of Management, and Stanford’s Graduate School of Business.  In 2014, Kaplan was elected to a three year term as INFORMS President-Elect (2015), President (2016), and Past-President (2017).  For more information about Kaplan and his research, visit

To request disability-related accommodations for this event, please contact the person listed above, or the unit hosting the event.