Summer School
The following distinguished speakers have accepted our invitation to give lectures in the summer school:
Gérard Cornuéjols (Carnegie Mellon University, Pittsburgh)
András Frank (Eötvös University, Budapest)
Thomas Rothvoß (University of Washington)
David Shmoys (Cornell University, Ithaca)
Attendance at the summer school requires registration.
Program:
Friday (June 20) | 13:00 - 14:15 | On-site registration (Arithmeum) |
14:15 - 14:30 | Welcome | |
14:30 - 16:00 | Lecture by Gérard Cornuéjols | |
16:00 - 16:30 | Coffee break | |
16:30 - 18:00 | Lecture by David Shmoys | |
18:00 - 19:00 | Arithmeum tour 1 | |
Saturday (June 21) | 09:30 - 10:00 | Coffee |
10:00 - 11:30 | Lecture by András Frank | |
11:30 - 13:30 | Lunch break | |
13:30 - 15:00 | Lecture by Gérard Cornuéjols | |
15:00 - 15:30 | Coffee break | |
15:30 - 17:00 | Lecture by Thomas Rothvoß | |
17:00 - 18:00 | Arithmeum tour 2 | |
Sunday (June 22) | 09:30 - 10:00 | Coffee |
10:00 - 11:30 | Lecture by David Shmoys | |
11:30 - 13:30 | Lunch break | |
13:30 - 15:00 | Lecture by András Frank | |
15:00 - 15:30 | Coffee break | |
15:30 - 17:00 | Lecture by Thomas Rothvoß | |
18:00 - 21:00 | IPCO Welcome reception (Arithmeum) | |
Mon - Wed (June 23 - 25) | IPCO Conference (University Club) |
Abstracts:
Gérard Cornuéjols: |
Cut-generating functions in integer programming Cutting planes have become a key component of integer programming solvers. Some of the most successful cutting planes are generated from an optimal tableau of the linear programming relaxation by applying a simple "cut-generating function". Gomory's mixed-integer cuts are a classical example. In these lectures, we present our current understanding of the theory of cut-generating functions. In particular we develop their relationship to lattice-free convex sets. |
András Frank: |
Constructive characterizations Given a graph property P, its constructive characterization is a building procedure consisting of simple steps so that a graph has property P if and only if it can be obtained from a small starting graph by applying the given procedure. A simple and well-known example is the ear-decomposition of strongly connected digraphs. A more complicated one is described by a theorem of Dirac stating that a simple graph is chordal if and only if it can be built up from a node by adding new nodes one by one in such a way that the currently added new node is connected to a clique of the already existing subgraph. Constructive characterizations often prove to be surprisingly powerful in deriving otherwise difficult theorems. For example, a constructive characterization of 2k-edge-connected graphs gives rise to an immediate proof of the famous orientation theorem of Nash-Williams. An analogous characterization of k-edge-connected digraphs easily implies a classic theorem of Edmonds on packing arborescences. In this mini-course, I overview the most important constructive characterizations and exhibit some of their several exciting applications. |
Thomas Rothvoß: |
Extended formulations A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. We will review the basic definitions and concepts in the field of extended formulations and see several examples of compact extended formulations. Then we will discuss Yannakakis Theorem and the award winning result of Fiorini, Massar, Pokutta, Tiwary and de Wolf that the TSP polytope requires exponential size LPs. Afterwards, we discuss a recent exponential lower bound on the matching polytope. |
David Shmoys: |
Improving Christofides' algorithm with randomization and LP 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. We shall briefly discuss recent results of Oveis Gharan, Saberi, & Singh and Mömke & Svensson for the graphical TSP, Asadpour, Goemans, Mądry, Oveis Gharan, & Saberi for the asymmetric TSP, but we shall focus instead on results for the s-t path traveling salesman problem. In the s-t 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 subsequent improvement by SebÅ‘, which gives a refinement of this approach that yields a 1.6-approximation algorithm. Finally, 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. |