Georgia Institute of Technology College of Sciences

In this work we study the ruin problem for a generalized Cramer-Lundberg reserve model with investments, under the modeling (volatility and claim intensity) uncertainty. We formulate the problem in terms of the newly developed theory on G-Expectation, initiated by S. Peng (2005). More precisely, we recast the problem as to determine the ruin probability under a G-expectation for a reserve process with a G-Compound Poisson type claim process, and perturbed by a G-Brownian motion. We show that the Lundberg bounds for a finite time ruin probability can still be obtained by an exponential $G$-martingale approach, and that the asymptotic behavior of the ruin, as the initial endowment tends to infinity, can be analyzed by the sample path large deviation approach in a G-expectation framework, with respect to the corresponding storage process. This is a joint work with Xin Wang.

A multivariate real polynomial p(x) is nonnegative if p(x) is at least 0 for all x in R^n. I will review the history and motivation behind the problem of representing nonnegative polynomials as sums of squares. Such representations are of interest for both theoretical and practical computational reasons, with many applications some of which I will present. I will explain how the problem of describing nonnegative polynomials fits into convex algebraic geometry: the study of convex sets with underlying algebraic structure, that brings together ideas of optimization, convex geometry and algebraic geometry. I will end by presenting current research problems in this area.

The traveling salesman problem (TSP) is the most famous problem in discrete optimization. Given $n$ cities and the costs $c_{ij}$ for traveling from city $i$ to city $j$ for all $i,j$, the goal of the problem is to find the least expensive tour that visits each city exactly once and returns to its starting point. We consider cases in which the costs are symmetric and obey the triangle inequality. In 1954, Dantzig, Fulkerson, and Johnson introduced a linear programming relaxation of the TSP now known as the subtour LP, and used it to find the optimal solution to a 48-city instance. Ever since then, the subtour LP has been used extensively to find optimal solutions to TSP instances, and it is known to give extremely good lower bounds on the length of an optimal tour. Nevertheless, the quality of the subtour LP bound is poorly understood from a theoretical point of view. For 30 years it has been known that it is at least 2/3 times the length of an optimal tour for all instances of the problem, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in 30 years in tightening these bounds. In this talk we will review some of the results that are known about the subtour LP, and give some new results that refine our understanding in some cases. In particular, we resolve a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case. We also begin a study of the subtour LP bound for the extremely simple case in which all costs $c_{ij}$ are either 1 or 2. For these instances we can show that the subtour LP is always strictly better than 3/4 times the length of an optimal tour. These results are joint work with Jiawei Qian, Frans Schalekamp, and Anke van Zuylen.

An important structural feature of the kth homology group of SL_n(Z) is that it is independent of n once n is sufficiently large. This property is called "homological stability" for SL_n(Z). Congruence subgroups of SL_n(Z) do not satisfy homological stability; however, I will discuss a theorem that says that they do satisfy a certain equivariant version of homological stability.