[Colloquium] Abie Flaxman talk tomorrow 12:15 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker: Abraham Flaxman
Carnegie Mellon University 
Speaker 's Homepage: http://www.math.cmu.edu/~adf/

Time: Thursday, June 7th 2004, 12:15 p.m. 
Place: TTI-C (1427 E. 60th St. – 2nd Floor) 
LUNCH PROVIDED 
  
Title: Two stage stochastic programming on average: Minimum Spanning Trees

Abstract: In real-life optimization, the costs and constraints are sometimes not
known exactly. Stochastic programming is one approach used in these situations.

Designing minimum spanning trees is a classical problem in combinatorial
optimization. A remarkable fact about average case minimum spanning trees is
that when the cost of the edges between n nodes are selected independently and
uniformly from [0,1], the cost of the MST converges to a constant, and the
constant is \zeta(3) = 1/1^3 + 1/2^3 + 1/3^3 + ....

In the two-stage stochastic programming version of this problem, known are the
costs of each edge on Monday and the distribution of the costs of each edge on
Tuesday. The goal is to select a set of edges to buy on Monday so that when the
tree is completed on Tuesday, the expected total cost is minimized.

This talk will focus on the two-stage version where the Monday and Tuesday costs
are all selected independently and uniformly from [0,1]. In this case, a simple
threshold heuristic produces a solution with expected cost \zeta(3) - 1/2. This
is not the optimal two-stage solution, however.
 

If you have questions, or would like to meet the speaker, please contact 
Meridel at 4-9873 or mtrimble at tti-c.org 
   
For information on future TTI-C talks or events, please go to the TTI-C Events 
page: http://www.tti-c.org/events.shtml