MIT Electrical Engineering and Computer Science EECS Event

Getting Across Town by Bus

Michael Mitzenmacher
Professor, Harvard University

Tuesday, September 11, 2001
4:00 PM (reception following)
37-212
LIDS Colloquium

Abstract

In the bus network problem, the goal is to generate a plan for getting from point X to point Y within a city using buses in the smallest expected time. Because bus arrival times are not determined by a fixed schedule but instead may be random, the problem requires more than standard shortest path techniques. In recent work, Datar and Ranade provide algorithms in the case where bus arrivals are assumed to be independent and exponentially distributed.

We provide a polynomial time algorithm for a much wider class of arrival distributions, namely those with increasing failure rate. This class includes not only exponential distributions but also uniform, normal, and gamma distributions.

This initial work suggests important connections between distribution properties and stopping rule problems. We show how to build on this paradigm by describing subsequent work using similar techniques to handle aggregation problems, which arise for example in meta-search engines.