[Colloq] Reminder: Hiring Talk - Today, Tuesday, March 15, Robert Kleinberg- MIT

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Robert Kleinberg
MIT

Who will speak on:
Adaptive Algorithms for Price-setting and Overlay Routing

Tuesday, March 15, 2005
11:00am
366 West Village H
Northeastern University

Abstract:
Problems of sequential decision-making under partial information
commonly arise in the design of algorithms for networked systems and the
applications they support.  In such tasks, a decision-maker must
repeatedly choose from a set of alternatives, given only partial
knowledge of the past costs or benefits of these alternatives and no
knowledge of the future.  Classically, such problems have been modeled
as "multi-armed bandit problems," and they have been extensively studied
and applied in a broad range of contexts including machine learning
theory, economics, game theory, and the design of experiments.

We consider two such problems, motivated by applications to routing in
overlay networks and pricing in e-commerce, respectively. These two
problems are unified by the underlying decision-making model, and each
requires the development of new techniques within this framework. The
first problem involves choosing a series of routes between two nodes in
a network with time-varying edge delays, so as to minimize the average
delay.  The second involves adaptively pricing a commodity through a
sequence of transactions with different buyers.  A major limitation of
existing approaches based on the multi-armed bandit problem is their
dependence on the number of available alternatives, which renders them
inefficient if this number is exponential (e.g. the number of routing
paths between two nodes in a network) or infinite (e.g. a one-parameter
interval of prices).  In this talk we introduce new algorithms and lower
bound techniques which overcome this limitation, using ideas from linear
algebra, probability, and statistics.  This leads to the first provably
efficient algorithm for adaptive routing with end-to-end feedback, and
the first nearly tight characterization of the value of knowing the
demand curve in online posted-price mechanisms.

Parts of this talk represent joint work with Baruch Awerbuch and with
Tom Leighton.

BIO: Robert Kleinberg is a fifth-year Ph.D. student in the Computer
Science and Artificial Intelligence Laboratory at M.I.T., working under
the advisorship of Tom Leighton.  He is a recipient of the Fannie and
John Hertz Foundation Fellowship.  His research interests include
economic aspects of algorithms, online learning and its applications,
and optimization problems in network routing.  From 1999 to 2002, he
worked for Akamai Technologies, developing technologies for Internet
mapping and streaming media content delivery.

HOST: Rajmohan Rajaraman