log in  |  register  |  feedback?  |  help
PhD Proposal: Algorithm Design for Stochastic Optimization
Pan Xu
Monday, July 24, 2017, 10:00-11:30 am Calendar
  • 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)

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



This talk is organized by Jennifer Story