“Algorithms for Network Flows”

Neil Olver
Vrije Universiteit Amsterdam and CWI.

» In this series of lectures, we will discuss algorithms for maximum
flow, minimum cost flow, and generalized flow (where flow is scaled as
it traverses arcs). Flow problems are amongst the most important in
combinatorial optimization, and there is a huge body of literature on
the topic. We will focus on combinatorial algorithms, and especially
strongly polynomial algorithms. This means that the number of
arithmetic operations depend only on the size of the network, and not
on the sizes of the numbers used to encode capacities and costs. While
many of the algorithms we will discuss are quite classical, we will
work towards very recent results on strongly polynomial algorithms for
generalized flow maximization.»


“Approximation algorithms for the traveling salesman problem (and related recent advances) “

David Shmoys
Cornell University, USA.
«We will survey a number of recent results that yield improved approximation algorithms for variants of the traveling salesman problem (TSP); an r-approximation algorithm for an optimization is a polynomial-time algorithm that is guaranteed to find a feasible solution of objective function value within a factor of r of optimal. The common unifying theme throughout these lectures will be the role of randomization and linear programming in advancing the state of the art in this area over the past five years. We shall briefly discuss recent results of Oveis Gharan, Saberi, & Singh and Mömke & Svensson for the graphical TSP, as well as the result of Asadpour, Goemans, Mądry, Oveis Gharan, & Saberi for the asymmetric TSP in greater detail. We shall focus next on results for the st path traveling salesman problem.  In the st path TSP, we are given pairwise distances among n points that satisfy the triangle inequality, and two specified endpoints s and t; the problem is to find a shortest Hamiltonian path between s and t. Hoogeveen showed that the natural variant of the classic TSP algorithm of Christofides is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We shall present a result of An, Kleinberg, and Shmoys, which provides an approximation algorithm that is guaranteed to find a solution of cost within a factor of the golden ratio of optimal in polynomial time for any metric input. This result is based on modifying Christofides’ algorithm so that it randomly chooses the initial spanning tree based on an optimal solution to a natural linear programming relaxation, rather than a minimum spanning tree; this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides’ algorithm variant. We shall discuss a number of subsequent improvements, first by Sebő, who gives a refinement of this approach that yields a 1.6-approximation algorithm. We present an elegant result of Gao, that provides a much simpler approach to match a result of Sebő and Vygen that gives a 1.5-approximation algorithm for the graphical metric case of this problem. Finally, we briefly outline the most recent improvements made by Gottschalk & Vygen, and by Sebő & Van Zuylen.»

“Computing the Volume in High Dimension” (en español)

Santosh Vempala
Georgia Tech, USA.

«El problema del cálculo del volumen en dimensión alta es un problema antiguo, básico y difícil.  Esta muy conectado con los problemas de optimización, aprendizaje y muestreo al azar. En las ultimas tres  décadas, la investigación de algoritmos para calcular el volumen ha resultado en técnicas profundas para algoritmos en general y también
para las matemáticas de dimensión alta. Este curso tiene cuatro partes:

(1) introducción a los problemas, el modelo y la estructura de objetos

(2) Algoritmos y reducciones

(3) Geometría Convexa asintótica y

(4) Paseos aleatorios geométricos y sus análisis.»