PhD Proposal: Algorithm Design for Stochastic Optimization

Pan Xu
07.24.2017 10:00 to 11:30
AVW 3258

The stochastic versions of matching models are quiet useful in various domains such as kidney exchange, online dating, online advertising business and online crowdsourcing markets. In this proposal, we mainly consider the following three problems.
The first problem is called Stochastic Matching (SM), where each vertex has an integral patience and each edge has an existence probability. We need to probe each edge sequentially to see its existence (occurring independently according to its existence probability) while ensuing each vertex is probed no more than its patience, which is given as the input. Our goal is to output a matching with the maximum expected weight. We propose a simple randomized algorithm for SM on a general graph and improve current best ratio from $3.71$ to $3.22$.
The second is Stochastic Hypergraph Matching (SHM), where each edge has an independent existence probability but no patience constraint. Our task is to probe each edge sequentially to output a hypermatching with a maximum expected weight. We focus on SHM on a $k$-uniform hypergraph and proposed two LP-based algorithms, which achieve a ratio of $k+1/2+o(1)$ and $k+\epsilon$ respectively for any given $\epsilon>0$. This is very close to the integrality gap of our benchmark LP, which is at least $k-1+1/k$.
The third is Online Matching (OM). The basic setting is captured by a bipartite graph, where one set of vertices is offline and the other is online. Once a vertex from the online side arrives, we need to make an immediate and irrevocable decision: either reject it or match it to one of its neighbors. We focus on two different variants of OM under the setting of Known IID: edge-weighted and vertex-weighted, and present several online algorithms with improved competitive ratios.
Examining Committee: Chair: Dr. Aravind Srinivasan Dept rep: Dr. John Dickerson Members: Dr. Samir Khuller