PhD Proposal: Matching Under Uncertainty

Graph matching forms a fundamental computational problem that can be used in many wide-ranging applications such as resource allocation, e-commerce, kidney exchange, ad placement, and ride-sharing. While the most classical version of this problem is well understood, many real-world applications involve uncertainty in the input data, and classical algorithms cannot be directly applied to these settings.For instance, in many applications the full set of vertices of the graph is not known in advance, but instead revealed to the algorithm in discrete stages. For instance, in ad placement applications, users arrive one by one, and neither the users nor their order of arrival is known to the algorithm a priori. The many variants of the online matching problem model such situations and capture real-world problems such as e-commerce, ad allocation, and ride-sharing. This family of problems is far less well understood than the classical (offline) matching problem.Additionally, we consider stochastic variants, wherein the edge set of the graph is unknown and random. This models uncertainty in the success or quality of a match: for instance, in the ad allocation application, it is unknown a priori whether a user will click on an ad (and, thus, if revenue will be earned, in the pay-per-click model).We propose to study such variants of graph matching and develop efficient algorithms with state-of-the-art theoretical guarantees.Examining Committee:

Chair:Department Representative:

Dr. Aravind Srinivasan Dr. Soheil FeiziDr. Will Ma (Columbia University)Dr. John Dickerson