Title: LP based approximation algorithm for an stochastic matching problem
| Speaker: | David Aleman |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Consider the random graph model where each edge e has a fixed weight w_e and it is independently present in the graph with probability p_e. Given these probabilities, we want to construct a maximum weight matching in the graph. One can only determine if an edge is present by querying it, and if an edge is present, it must be irrevocably included in the matching. Additionally, each vertex i can be queried no more than t_i times. The goal is to device an adaptive policy (algorithm) to query the edges of the graph one by one in order to maximize the expected weight of the matching.
In this talk we present an elegant LP-based constant-factor approximation algorithm with respect to the optimal adaptive policy for the problem.
This is one of the results due to Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra, in their paper "When LP is the Cure for your Matching Woes" from 2011.