Selected Work: (for a complete list please click here)
- Kidney Exchange in Dynamic Sparse Heterogenous Pools, with
Patrick Jaillet, and
Michael A. Rees,
Management Science (revise and resubmit), 2014.
- Blogged about here.
- Extended abstract appeared in The 14th ACM Conference in Electronic Commerce (EC), 2013. [slides in pdf]
- Summary: One of the main challenges in the current practice of kidney exchange is matching highly sensitized patients. These patients are very unlikely to be compatible with a random donor.
Current pools of patient-donor pairs are not too large and they contain many such hard-to-match patients. Therefore, the compatibility graphs associated with these pools are sparse (or sometimes called thin).
One way to create a thicker pool is to wait for many pairs to join before matching (finding a set of disjoint exchanges), and a major decision clearinghouses are facing is how often to search for allocations.
On one hand, waiting is costly; while patients are waiting, they are on dialysis and their health conditions deteriorate. On the other hand, in the current programs, matching too frequently may reduce the number of matched pairs, especially highly sensitized ones.
In this project, we study this intrinsic tradeoff between the waiting time and the number of matches by analyzing a class of algorithms (which are used in practice) that search periodically for allocations.
We perform sensitivity analysis on the amount of waiting given different types of allocations (using 2-ways, 3-ways, or chains).
We find that if only 2-way cycles are conducted, in order to gain a significant amount of matches over the online scenario (matching each time a new incompatible pair joins the pool) the waiting period should be very long.
If 3-way cycles are also allowed we find regimes in which waiting for a short period also increases the number of matches considerably.
Finally, a significant increase of matches can be obtained by using even one non-simultaneous chain while still matching in an online fashion.
Our theoretical findings (based on random graph models and motivated by clinical data) and computational experiments (using clinical data from some of the largest exchange programs in the US) lead to policy recommendations.
- Software: Kidney Exchange Developed primarily by
Itai Ashlagi. Please check his homepage for instructions and updates.
- Online Stochastic Matching: Online Actions Based on Offline Statistics, with
Shayan Oveis Gharan and
Mathematics of Operations Research, November 2012 37:559-573.
- Conference version appeared in The 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. [slides in pdf]
- Summary: In display advertising, ad servers sell impressions (display of an ad on a webpage viewed by a user) to advertisers.
Each advertiser wishes to only advertise in certain webpages, and these preferences can be encoded by a bipartite graph.
When a webpage is viewed the ad server needs to make an online (irrevocable) decision on which ad to display, with the goal of maximizing its revenue.
The matching problem for this online market can be modeled as an online bipartite matching problem.
Traditionally, in online matching, we assume that an adversary determines the graph and the sequence of arrivals (webpage views in display advertising).
However, advertising companies, like Google, have knowledge on the underlying bipartite graph.
Further they have historical data on the webpage views to construct stochastic traffic models that approximate the real traffic better than the adversarial model.
Given this technology, the important research question is how to use this information to design online algorithms with performance guarantees superior to what we can achieve in an adversarial model.
In this paper, we develop the first algorithm that improves the performance guarantee for the stochastic version of the online matching problem in its general form.
A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling, and to use those offline statistics to guide the decisions of the online algorithm.
- Dynamic Stochastic Optimization of Relocations in Container Terminals, with
Cynthia Barnhart, and
working paper, 2013.
- Summary: Worldwide container transportation has been growing considerably over the past few decades.
As the volume of container shipments increases, it creates higher demand on terminal (or port) optimization and management.
One of the challenges in the port operations is the efficiency loss due to unproductive (or un-billable) moves that happen in the yard (or the storage area).
In terminals, containers are stacked on top of each other, and to retrieve the target container, sometimes other containers need to be relocated.
Currently, in some busy terminals, up to 30% of moves in the yard are unproductive.
The main challenges in optimizing the number of relocations lie in making real time decisions for dynamically stacking and retrieving containers under uncertainty on containers arrival/departure times.
In this work, we give a mathematical model and (large-scale) integer program to minimize the number of relocations in a dynamic setting.
Further, using a two-stage stochastic optimization framework, we show that lack of information (on arrival/departure sequences) results in more relocations.
More importantly, we show that having partial information significantly closes the gap to the solution with complete information.
Such information can be obtained by mining the historical data and by constructing forecasting models.
- Software: DCRP Developed by