TITLE: Incomplete Information and Large Dimensionality in Decision Making

SPEAKER: Marco Molinaro

ABSTRACT:

This talk explores from different perspectives two main sources of difficulty in decision making: incomplete information and large dimensionality. In the first part, I will talk about optimization under uncertainty, more specifically resource allocation with item uncertainty. I will focus on the Online Packing IP model, where columns of the IP (i.e. items) come one-by-one in random order. This, and related models, have wide application in revenue management, e.g. airline booking and online advertisement allocation. Combining ideas from learning theory and geometric insights, we provide a strategy that is able to better cope with uncertainty and the first with guarantees that do not degrade as the number of items increases.

In the second part of the talk, I will address other perspectives on decision making. I will briefly discuss sublinear algorithms, which tradeoff the amount of information used to perform a computational task and the quality of the solution obtained. These are crucial in an increasing number of applications that involve massive data, ranging from biology to network analysis. Finally, I will discuss some of my work on Integer Programming, a classical tool for dealing with large decision spaces of combinatorial problems. Here, I will highlight our advances on the construction and analysis of cutting planes, a crucial piece of solving Integer Programs in practice, where we (partially) resolve several questions raised in the literature.