Georgia Institute of Technology College of Sciences

I will first discuss the motivation and background information necessary to study the subjects of branched covers and of contact geometry. In particular we will give some examples and constructions of topological branched covers as well as present the fundamental theorems in this area. But little is understood about the general constructions, and even less about how branched covers behave in the setting of contact geometry, which is the focus of my research. The remainder of the talk will focus on the results I have thus far and current projects.

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate deeper cuts in a non-recursive fashion. (This talk is based on joint work with Francois Margot.)

In this presentation, we show a significant role that symmetry, a fundamental concept in convex geometry, plays in determining the power of robust and finitely adaptable solutions in multi-stage stochastic and adaptive optimization problems. We consider a fairly general class of multi-stage mixed integer stochastic and adaptive optimization problems and propose a good approximate solution policy with performance guarantees that depend on the geometric properties such as symmetry of the uncertainty sets. In particular, we show that a class of finitely adaptable solutions is a good approximation for both the multi-stage stochastic as well as the adaptive optimization problem. A finitely adaptable solution specifies a small set of solutions for each stage and the solution policy implements the best solution from the given set depending on the realization of the uncertain parameters in the past stages. To the best of our knowledge, these are the first approximation results for the multi-stage problem in such generality. (Joint work with Vineet Goyal, Columbia University and Andy Sun, MIT.)

Lopsided bipartite graphs naturally appear in advertising setting. One side is all the eyeballs and the other side is all the advertisers. An edge is when an advertiser wants to reach an eyeball, aka, ad targeting. Such a bipartite graph is lopsided because there are only a small number of advertisers but a large number of eyeballs. We give algorithms which have running time proportional to the size of the smaller side, i.e., the number of advertisers. One of the main ideas behind our algorithm and as well as the analysis is a property, which we call, monotonic quality bounds. Our algorithm is flexible as it could easily be adapted for different kinds of objective functions. Towards the end of the talk we will describe a new matching polytope. We show that our matching polytope is not only a new linear program describing the classical matching polytope, but is a new polytope together with a new linear program. This part of the talk is still theoretical as we only know how to solve the new linear program via an ellipsoid algorithm. One feature of the polytope, besides being intriguing, is that it has some notion of fairness built in. This is important for advertising since if an advertiser wants to reach 10 million users of type A or type B, advertiser won't necessarily be happy if we show the ad to 10 million users of type A only (though it fulfills the advertising contract in a technical sense).