The Colloquium Series of the
              Department of Computer Science,
		  University of Wyoming

			presents

                    Dr. Russell Bent
	            Brown University

"Online Stochastic Optimization Under Time Constraints"

                  Thursday, April 28, 2005
	                ENG 4066
	             3:00 - 4:00 p.m.

Abstract:

Recent advances in both computational power and communications
technologies have created novel opportunities for research in
combinatorial optimization. Many applications in routing, scheduling,
and networking raise exciting challenges, in particular in uncertainty.
These applications are often online optimization problems, where the
input is not known a priori, but characterized by a probabilistic model,
and where decisions are made under severe time constraints. This talk
presents an online stochastic optimization framework whose goal is to
maximize expected profit. It presents two algorithms, consensus and
regret, designed to operate under severe time constraints. Theoretical
results show that the framework and algorithms provide strong guarantees
on solution quality (under reasonable assumptions about the input
distribution). Moreover, experimental results on a variety of
applications, like packet scheduling and vehicle routing, indicate
that the approach provides significant improvements in quality of
service, even under severe time constraints.

URL: http://www.cs.brown.edu/people/rbent/