[Colloquium] TTIC Talks: Ravishankar Krishnaswamy, CMU

[Liv Leader]

When:     Monday, February 6 @ 11 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, Room #526

Who:       Ravishankar Krishnaswamy, CMU

Title: Approximation Techniques for Stochastic Optimization Problems

Abstract:

In this talk we will present approximation algorithms (and general
techniques) for some basic problems in the field of stochastic
optimization. A canonical problem is stochastic knapsack: we are given
a knapsack of size B, and a collection of items, where
the items have stochastic sizes and rewards (the distributions are
known in advance). The goal is to devise an algorithm (i.e., a policy
which can adapt based on the realized sizes of previously inserted
items) to insert the next item to maximize the expected reward of
items successfully packed into the knapsack. The size and reward of
the item are realized only after the item is inserted.

This basic problem can be generalized along several different
directions. For example, if each of the stochastic jobs is more
generally a Markov Chain (and makes random transitions each time we
"play" it), we can then capture a class of (finite-horizon)
multi-armed bandit problems. Or if these jobs are located at different
vertices on a metric, we obtain stochastic routing and orienteering
problems.

While these problems have all received much attention in fields like
operations research and machine learning, the issue of their
approximability has been addressed only recently. In this talk, we
will present efficient approximation algorithms with near-optimal
guarantees for the (general) stochastic knapsack problem, the
stochastic orienteering problem, and the multi-armed bandits problem.
To the best of our knowledge, prior work (and techniques) only handle
very special cases of the above problems. These results are based on
joint works with Anupam Gupta, Marco Molinaro, Viswanath Nagarajan,
and R. Ravi, and appeared at the FOCS 2011 and SODA 2012 conferences.

Towards the end, I will also briefly discuss some of my other research
in areas such as network design and scheduling.  Finally, I will
conclude by discussing the future directions in the above areas.

Host: Yury Makarychev: yury at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120131/0f1a8b65/attachment.htm