Georgia Institute of Technology College of Sciences

For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a "black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm: http://arxiv.org/abs/1210.4594 In the interest of covering all the ideas, we will assume that the audience is familiar with basic notions such as augmenting paths and bipartite matching algorithm.

I will present two related 30-minute talks. Title 1: Generalized Online Matching with Concave Utilities Abstract 1: In this talk we consider a search engine's ad matching problem with soft budget. In this problem, there are two sides. One side is ad slots and the other is advertisers. Currently advertisers are modeled to have hard budget, i.e., they have full utility for ad slots until they reach their budget, and at that point they can't be assigned any more ad-slots. Mehta-Saberi-Vazirani-Vazirani and Buchbinder-J-Naor gave a 1-1/e approximation algorithm for this problem, the latter had a traditional primal-dual analysis of the algorithm. In this talk, we consider a situation when the budgets are soft. This is a natural situation if one models that the cost of capital is convex or the amount of risk is convex. Having soft budget makes the linear programming relaxation as a more general convex programming relaxation. We still adapt the primal-dual schema to this convex program using an elementary notion of convex duality. The approximation factor is then described as a first order non-linear differential equation, which has at least 1-1/e as its solution. In many cases one can solve these differential equations analytically and in some cases numerically to get algorithms with factor better than 1-1/e. Based on two separate joint works, one with Niv Buchbinder and Seffi Naor, and the other with Nikhil Devanur. Title 2: Understanding Karp-Vazirani-Vazirani's Online Matching (1990) via Randomized Primal-Dual. Abstract 2: KVV online matching algorithm is one of the most beautiful online algorithms. The algorithm is simple though its analysis is not equally simple. Some simpler version of analysis are developed over the last few years. Though, a mathematical curiosity still remains of understanding what is happening behind the curtains, which has made extending the KVV algorithm hard to apply to other problems, or even applying to the more general versions of online matching itself. In this talk I will present one possibility of lifting the curtains. We develop a randomized version of Primal-Dual schema and redevelop KVV algorithm within this framework. I will then show how this framework makes extending KVV algorithm to vertex weighted version essentially trivial, which is currently done through a lot of hard work in a brilliant paper of Aggarwal-Goel-Karande-Mehta (2010). Randomized version of Primal-Dual schema was also a missing technique from our toolbox of algorithmic techniques. So this talk also fills that gap.

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. This problem has a rich history of study in both statistics and, more recently, in CS Theory and Machine Learning. We present a polynomial time algorithm for this problem (running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy), with provably minimal assumptions on the Gaussians. Prior to this work, it was unresolved whether such an algorithm was even information theoretically possible (ie, whether a polynomial amount of data, and unbounded computational power sufficed). One component of the proof is showing that noisy estimates of the low-order moments of a 1-dimensional mixture suffice to recover accurate estimates of the mixture parameters, as conjectured by Pearson (1894), and in fact these estimates converge at an inverse polynomial rate. The second component of the proof is a dimension-reduction argument for how one can piece together information from different 1-dimensional projections to yield accurate parameters.

A well-known conjecture of Lovasz and Plummer asserts that the number of perfect matchings in 2-edge-connected cubic graph is exponential in the number of vertices. Voorhoeve has shown in 1979 that the conjecture holds for bipartite graphs, and Chudnovsky and Seymour have recently shown that it holds for planar graphs. In general case, however, the best known lower bound has been until now barely super-linear. In this talk we sketch a proof of the conjecture. The main non-elementary ingredient of the proof is Edmonds' perfect matching polytope theorem. This is joint work with Louis Esperet, Frantisek Kardos, Andrew King and Daniel Kral.