[Colloquium] Martin Pal talk Wednesday 2:45 at TTI-C

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK

Speaker: Martin Pal
AT&T Labs
Speaker 's Homepage:  http://www.cs.cornell.edu/People/mpal/

Time: Wednesday, April 21st  2004, 2:45pm
Place: TTI-C (1427 E. 60th St. – 2nd Floor)

Title: Stochastic Optimization, Mechanism Design and Cost Sharing 

Abstract: The design of transportation, communication and information networks
and infrastructure is a rich source of combinatorial optimization problems that
are both theoretically interesting and of great practical importance. Many of
these problems are naturally phrased in terms of users: each user has a certain
requirement, and our goal is to design infrastructure to satisfy all their
requirements. For example in the Steiner Tree problem, the users are the
terminals and require to be connected to a central server node; in facility
location problems, each user wants to be supplied from a nearby open facility. 

In the first part of the talk, I want to focus on techniques to deal with
stochastic variants of these problems, in which the demands of users are not
known in advance, but come from a probability distribution. I will show a simple
technique that allows us to take approximation algorithms for deterministic
problems, and convert them into algorithms for their stochastic counterparts.
Our model is a two-stage stochastic model with recourse: we are allowed to build
a partial, anticipatory solution at low per unit cost before user demands are
known. After the demands are revealed, we must complete the solution (at higher
cost) to satisfy all users. 

In the second part of the talk, I will look at optimization from an economic
perspective. Assuming that each user derives a certain value from her
requirements being satisfied, which users should we satisfy and what price
should we ask for doing so? Much of the previous workstrives to achieve social
optimality, often at the expense of enormous costs for the service provider. In
contrast, our primary concern is to ensure that the service provider does not
run into a (too large) deficit, while not overcharging the users. We give
mechanisms for some network design problems that are approximately budget
balanced and group strategyproof. 

Parts of the talk are joint work with Anupam Gupta, R. Ravi and Amitabh Sinha;
and Eva Tardos. 


Bio: 
Martin Pal graduated from Comenius University in Slovakia in 2000 with a
"magister" degree (roughly coresponding to masters). In August he joined the CS
department at Cornell to work on his PhD degree. He is expected to graduate by
August 2004. His interests include theoretical computer science, combinatorial
optimization, and game theory. 

As an undergraduate, he was involved in many programming competitions, both as a
coach and contestant. He was a volunteer staff member of the Correspondence
Seminar in Programming for high school students, member of the Scientific
Committee of the Slovak Olympiad in Informatics, and a founding member of the
Internet Problem Solving Contest <http://ipsc.ksp.sk>. At Cornell, he is a coach
of the Cornell ACM Programming Contest team. For three semesters, he also
organized a Theory Discussion Group, a weekly meeting of students interested in
CS theory.

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