Georgia Institute of Technology College of Sciences

I will describe a simple scheme for generating a valid inequality for a stochastic integer programs from a given valid inequality for its deterministic counterpart. Applications to stochastic lot-sizing problems will be discussed. This is joint work with Yongpei Guan and George Nemhauser and is based on the following two papers (1) Y. Guan, S. Ahmed and G.L. Nemhauser. "Cutting planes for multi-stage stochastic integer programs," Operations Research, vol.57, pp.287-298, 2009 (2) Y. Guan, S. Ahmed and G. L. Nemhauser. "Sequential pairing of mixed integer inequalities," Discrete Optimization, vol.4, pp.21-39, 2007 This is a joint DOS/ACO seminar.

In this talk Professor Tapia identifies elementary mathematical frameworks for the study of popular drag racing beliefs. In this manner some myths are validated while others are destroyed. Tapia will explain why dragster acceleration is greater than the acceleration due to gravity, an age old inconsistency. His "Fundamental Theorem of Drag Racing" will be presented. The first part of the talk will be a historical account of the development of drag racing and will include several lively videos.

After reviewing a few techniques from the theory of confoliation in dimension three we will discuss some generalizations and certain obstructions in extending these techniques to higher dimensions. We also will try to discuss a few questions regarding higher dimensional confoliations.

We consider the #P complete problem of counting the number of independent sets in a given graph. Our interest is in understanding the effectiveness of the popular Belief Propagation (BP) heuristic. BP is a simple and iterative algorithm that is known to have at least one fixed point. Each fixed point corresponds to a stationary point of the Bethe free energy (introduced by Yedidia, Freeman and Weiss (2004) in recognition of Hans Bethe's earlier work (1935)). The evaluation of the Bethe Free Energy at such a stationary point (or BP fixed point) leads to the Bethe approximation to the number of independent sets of the given graph. In general BP is not known to converge nor is an efficient, convergent procedure for finding stationary points of the Bethe free energy known. Further, effectiveness of Bethe approximation is not well understood. As the first result of this paper, we propose a BP-like algorithm that always converges to a BP fixed point for any graph. Further, it finds an \epsilon approximate fixed point in poly(n, 2^d, 1/\epsilon) iterations for a graph of n nodes with max-degree d. As the next step, we study the quality of this approximation. Using the recently developed 'loop series' approach by Chertkov and Chernyak, we establish that for any graph of n nodes with max-degree d and girth larger than 8d log n, the multiplicative error decays as 1 + O(n^-\gamma) for some \gamma > 0. This provides a deterministic counting algorithm that leads to strictly different results compared to a recent result of Weitz (2006). Finally as a consequence of our results, we prove that the Bethe approximation is exceedingly good for a random 3-regular graph conditioned on the Shortest Cycle Cover Conjecture of Alon and Tarsi (1985) being true. (Joint work with Venkat Chandrasekaran, Michael Chertkov, David Gamarnik and Devavrat Shah)