The seminar will be dedicated to the study of online optimization problems, where the demands are given by a probability distribution, e.g., for online Steiner tree if at each time instant, the demand vertex is a  uniformly random vertex from the graph, which needs to be  connected before the next (random) vertex arrives. In this paper, we show that one can beat the tight logarithmic bound known for online Steiner tree, i.e., we prove that if each demand vertex is an independent draw from some probability distribution, a variant of the natural greedy algorithm achieves an average cost that is at most a constant away from the average optimal cost; we show how this result can be extended to some other subadditive problems as well.  Furthermore, we show that the assumptions that the input sequence consists of independent draws and that the distribution is known to the algorithm are both essential; we show logarithmic lower bounds if either assumption is violated.

As an application of the ideas above, we show how to give an average-case analysis of the Universal TSP problem. Moreover, we give preliminary results on extending the Steiner tree results above to the related ``expected ratio'' measure.

Joint work with Naveen Garg, Anupam Gupta and Stefano Leonardi