Talks

PhD Proposal: Matching Under Uncertainty

Nathaniel Grammel

4107 Brendan Iribe Center for Computer Science and Engineering (IRB)

Wednesday, May 4, 2022, 10:00 am-12:00 pm

You are subscribed to this talk through .
You are watching this talk through .
You are subscribed to this talk. (unsubscribe, watch)
You are watching this talk. (unwatch, subscribe)
You are not subscribed to this talk. (watch, subscribe)

Abstract

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 Feizi
Dr. Will Ma (Columbia University)
Dr. John Dickerson

Bio

Nathaniel Grammel is a PhD student at the University of Maryland, advised by Professor Aravind Srinivasan. His research interests include approximation and online algorithms for stochastic and combinatorial optimization problems. Prior to attending the University of Maryland, he received his BS and MS from New York University.

This talk is organized by Tom Hurst