Title: Randomized Algorithms and Stochastic Requests for Min-Cost Perfect Matching With Delays
Advisors: Anna Karlin & Shayan Oveis Gharan
Supervisory Committee: Anna Karlin (Co-Chair), Shayan Oveis Gharan (Co-Chair), Chirstopher Hoffman (GSR, Math), and Dan Grossman
Abstract: In the "Minimum-Cost Perfect Matching with Delays" (MPMD) problem, a series of requests appear over time in a metric space. The goal is to pair requests to each other (online) with the objective of minimizing the sum of the distances between matched points plus the sum of the times the requests waited to be matched. We describe a common algorithmic technique for these problems (growing balls around the requests) which appears in: the best-known deterministic MPMD algorithm of Azar and Jacob-Fanani, our "odd-ball growing" algorithm (which matches the best-known behavior for randomized algorithms), and our new algorithm for requests drawn from a probability distribution. Finally, we discuss open MPMD-based problems for which ball growing may be a useful technique.
Based on joint work with Anna Karlin, Shayan Oveis Gharan and Alireza Rezaei.