4d778a02 
 XPost: cs.bboard, columbia.general.bboard 
 From: rocco@news.cs.columbia.edu 
  
 On Tuesday, February 22nd, at 2pm, Umesh Vazirani will give a special talk 
 at the theory seminar (abstract below). 
  
 Then on Thursday, February 24, at 1:30, Chaitanya Swami will give a joint 
 theory/IEOR seminar (abstract below). 
  
 Best, Rocco 
  
 __________________________________ 
  
 TALK: 
  Tuesday, February 22nd, 2005 
  2:00 pm -- 3:15 pm 
  Interschool Lab, 7th Floor CEPSR 
  
 SPEAKER: 
  Umesh Vazirani 
  UC Berkeley 
  
  
 ABSTRACT: 
   
  AdWords and Generalized Online Matching. 
  
 Search engine companies, such as Google, Yahoo and MSN, have 
 revolutionized the use of the Internet by individuals. Their 
 dramatic revenues are supported by a second revolution: 
 in the way businesses advertise to consumers. 
  
 I will talk about this lesser known revolution and the underlying 
 computational problem it raises. This problem is an elegant 
 generalization of the online bipartite matching problem. 
 I will describe two optimal algorithms for this task, each achieving a 
 competitive ratio of 1-1/e. The design of these algorithms is made 
 possible by the new notion of tradeoff-revealing linear programs. 
  
 Joint work with Aranyak Mehta, Amin Saberi and Vijay Vazirani 
  
 __________________________________ 
  
 TALK: 
  Thursday, February 24nd, 2005 
  1:30 pm -- 2:30 pm 
  303 Mudd 
  
 SPEAKER: 
  Chaitanya Swami  
  California Institute of Technology 
  
 ABSTRACT: 
  Approximation Algorithms for Stochastic Optimization 
   
 Stochastic optimization problems attempt to model uncertainty in the data 
 by assuming that (part of) the input is specified by a probability 
 distribution, rather than by deterministic data given in advance. We 
 consider the well-studied paradigm of stochastic recourse models, where 
 the uncertainty evolves through a series of stages and one can take 
 decisions in each stage in response to the new information learned. We 
 obtain the first approximation algorithms for a variety of 2-stage and 
 k-stage stochastic integer optimization problems where the underlying 
 random data is given by a "black box" and no restrictions are placed on 
 the costs of the two stages: one can merely sample data from this 
 distribution, but no direct information about the distributions is given. 
  
 Our results are based on two principal components. First, we give a fully 
 polynomial approximation scheme for solving a broad class of 2-stage and 
 k-stage linear programs, where k is not part of the input. This is based 
 on reformulating the stochastic linear program, which has both an 
 exponential number of variables and an exponential number of constraints, 
 as a compact convex program, and adapting tools from convex optimization 
 to solve the resulting program to near optimality. In doing so, a 
 significant difficulty that we must overcome is that even evaluating the 
 objective function of this convex program at a given point may be provably 
 hard. Second, we give a rounding approach for stochastic integer programs 
 that shows that an approximation algorithm for a deterministic analogue 
 yields, with a small constant-factor loss, provably near-optimal solutions 
 for the stochastic problem. Thus we obtain approximation algorithms for 
 several stochastic problems, including the stochastic versions of the set 
 cover, vertex cover, facility location, multicut (on trees) and 
 multicommodity flow problems. 
  
 In this talk, I will focus mainly on the 2-stage problem and briefly 
 discuss the ideas required to extend our results to the multi-stage 
 setting. 
  
 This is joint work with David Shmoys. 
  
 --- SoupGate-Win32 v1.05 
  * Origin: you cannot sedate... all the things you hate (1:229/2)