Consider the problem of assigning consultants to projects. Each consultant should be assigned a project, in such a way that the cost of these assignments is minimized. Cost could represent the travel time of the consultant to the project site, or the ability of the consultant to complete the task. This problem is an instance of the minimum-cost matching problem: one of the most important problems in computer science. Substantial previous work has lead to efficient algorithms to compute these matchings. However, the consultant-assignment problem is naturally online, in that we do not know what the list of projects will be in advance. Projects arrive one-by-one, and as each project appears we must assign a consultant. The requirement that we make assignments as we go, without prior knowledge of the list of projects, makes the problem substantially more difficult. Prior work (by Khuller, Mitchell, and Vazirani) has demonstrated that this problem is intractable if the costs are arbitrary. If the costs form a metric (satisfying symmetry and triangle inequality, for example distances along a sphere) then the best possible deterministic guarantee is that the cost of our matching is at most 2K-1 times the optimum, where K is the number of assignments. In this talk, I will describe the first randomized algorithm for the online matching problem. By using a simple randomized greedy technique combined with prior work in metric embeddings (in particular the result of Fakcharoenphol, Rao, and Talwar), I will guarantee that the cost of our matching is at most O(log3 K) times the optimum. This talk is based on the paper “Randomized Online Algorithms for Minimum Metric Bipartite Matching” which appeared at SODA 2006, and represents joint work with Akash Nanavati and Laura Poplawski.