Organizing Committee

• Mohammad Ghodsi
• Hamid Mahini
• Ehsan Valavi
• Mahdi Rezaei

Abstract
Motivated by problems in online display ad allocation, in the first part, we will survey recent developments in online stochastic allocation problems. In particular, we describe a 0.67-approximation algorithm for the online stochastic matching problem, a 1-ε approximation for general online stochastic packing programs, and an online 1-1/e competitive algorithm for online generalized assignment problems. We discuss training-based techniques based on solving the primal or dual programs using the stochastic information, the idea of power-of-two choices in online decision making, and describe primal-dual online competitive algorithms in this context.

In the second part, we study the relation between the integer linear programming models for a class of discrete optimization problems and their relaxations. I will introduce a new probabilistic technique for transforming the optimal solutions of these relaxed programs into the near-optimal solutions for the original discrete problems. The technique is based on sampling from the combinatorial structures hidden in such problems. This has applications in max-min fair allocation problems and assymetric TSP problem. In order to present the idea, I will go through a generalization of the Traveling Salesman Problem (TSP) and show how we can improve the worst-case performance guarantee for this problem after almost 30 years. We will also see other applications of this technique in assignment problems and fair resource allocation.
This part is based on "An O(log n / log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem", joint work with Michel Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi (SODA 2010), and "Rounding by Sampling" (Ph.D. Thesis, Stanford University, 2010).

Finally, we study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes, by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs has, in particular, how well they globally minimize diameter. Our perspective enables simpler and more general proofs that get at the heart of network creation games.

 IPM HOMEPAGE | IPM LIBRARY