Combinatorial Optimization Reading Group - Ian DeHaan

Title: Greedy algorithm for stochastic matching is a 2-approximatio

Abstract: We will discuss the greedy algorithm for the stochastic matching problem. In this problem, we are given an undirected graph where each edge is assigned a probability p_e in [0, 1] and each vertex is assigned a patience t_v in Z+. We begin each step by probing an edge e which is not adjacent to any edges in our matching. The probe will succeed with probability p_e, and if it does, we add e to our matching. Otherwise, we may not probe e again. We also may not probe edges adjacent to a vertex v more than t_v times. The goal is to maximize the number of edges we add to our matching. A greedy approach was shown to be a 4-approximation for stochastic matching in a previous talk by David Kalichman through analysis of a more general problem. In this talk, we will show that greedy is a 2-approximation for the special case of stochastic matching.