CS Colloquium

Speaker: Prof. Adam MeyersonTitle: Randomized Online Matching Abstract: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.Bio:Adam Meyerson received his PhD from Stanford University in Fall 2002, with a thesis on approximation algorithms for design of minimum-cost computer networks. He spent the 2002-2003 academic year as a postdoctoral fellow of the Center for Algorithmic Adaptation, Dissemination, and Integration (Aladdin ) at Carnegie-Mellon University. Dr. Meyerson co-organized a series of workshops on integrated logistics ,designed to bring
together researchers from computer science and operations research to discuss applications of facility location problems ranging from warehouse placement to database analysis to network design. He joined the faculty of UCLA in Fall of 2003.

Location: TBA

Audiences: Everyone Is Invited

Contact: Nancy Levien