The Summer School event will take place during the two days preceding the IPCO conference (that is, on June 24 & 25, 2017). All Summer School events will take place in the Math & Computer Building (MC) in room 5501.
The speakers are Aleksander Mądry, Anupam Gupta, and Sanjeeb Dash.
Saturday (June 24) | 8:50 - 9:00 | Welcome |
9:00 - 10:30 | Sanjeeb Dash - Lecture 1 | |
10:30 - 11:00 | Coffee Break | |
11:00 - 12:30 | Aleksander Mądry - Lecture 1 | |
12:30 - 2:00 | Lunch | |
2:00 - 3:30 | Anupam Gupta - Lecture 1 | |
3:30 - 4:00 | Coffee Break | |
4:00 - 5:30 | Sanjeeb Dash - Lecture 2 | |
Sunday (June 25) | 9:00 - 10:30 | Aleksander Mądry - Lecture 2 |
10:30 - 11:00 | Coffee Break | |
11:00 - 12:30 | Anupam Gupta - Lecture 2 | |
12:30 - 2:00 | Lunch | |
2:00 - 3:00 | Aleksander Madry - Lecture 3 | |
3:00 - 3:30 | Coffee Break | |
3:30 - 4:30 | Sanjeeb Dash - Lecture 3 | |
4:30 - 4:45 | Break | |
4:45 - 5:45 | Anupam Gupta - Lecture 3 |
Aleksander Mądry
Lecture notes & Slides: [L1], [L2], [L3]
Title and Abstract
Title: Graph Algorithms and Continuous Optimization
Abstract: Traditionally, we view graphs as purely combinatorial objects and tend to design our graph algorithms to be combinatorial as well. In fact, in the context of algorithms, "combinatorial" became a synonym of "fast". Recent work, however, shows that a number of such "inherently combinatorial" graph problems can be solved much faster using methods that are very "non-combinatorial". Specifically, by approaching these problems with tools and notions borrowed from linear algebra and, more broadly, from continuous optimization. A notable examples here are the recent lines of work on the maximum flow problem, the bipartite matching problem, and the shortest path problem in graphs with negative-length arcs. This series of lectures will explore basic concepts that underlie these developments. The topics covered will span key continuous optimization primitives such as gradient descent method, Newton's method and interior point method. We will also demonstrate how these tools can be applied to graph algorithms, using the maximum flow problem as illustration.
Bio
Aleksander Mądry is an associate professor in the MIT EECS Department. His research centers on algorithmic graph theory, continuous optimization, and understanding uncertainty in the context of optimization. Aleksander received his PhD from MIT in 2011 and, prior to joining the MIT faculty, he spent a year as a postdoctoral researcher at Microsoft Research New England and then almost three years on the faculty of EPFL. His work was recognized with a variety of awards, including an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, an ACM Doctoral Dissertation Award Honorable Mention, a George M. Sprowls Doctoral Dissertation Award, Google Research Award, and a number of best paper awards at FOCS/SODA/STOC conferences.
Anupam Gupta
Lecture notes & Slides: [L1], [L2], [L3]
Title and Abstract
Title: Approximation Algorithms for Stochastic Optimization
Abstract: In this set of lectures I will survey some ways to model stochastic optimization problems. These problems are often NP-hard (or worse), and I will discuss techniques used to develop approximation algorithms for these kinds of problems. Examples include two-stage stochastic optimization, stochastic knapsack and other stochastic packing problems, and some stochastic scheduling problems.
Bio
Anupam Gupta received his B.Tech degree in Computer Science from Indian Institute of Technology, Kanpur, and his PhD degree in Computer Science from the University of California, Berkeley. After a short stint at Lucent Bell Labs in Murray Hill, New Jersey, he joined Carnegie Mellon University in January 2003, where he is currently Professor in the Computer Science Department. His research interests are broadly in the area of algorithms, primarily in developing approximation algorithms for NP-hard optimization problems, in online algorithms, and in understanding the algorithmic properties of metric spaces. He has received an Alfred P. Sloan Research Fellowship, and the NSF Career award.
Sanjeeb Dash
Lecture notes & Slides: [L1]
Title and Abstract
Title: Cutting planes from extended formulations
Abstract: Cutting planes are essential tools for solving mixed-integer programs, and split cuts are among the most important cutting planes used in practical integer programming solvers. We discuss how to use extended formulations of the LP relaxation of a mixed-integer program to obtain stronger cutting planes than those that can be obtained from the original LP relaxation. In particular, we compare the effect of adding split cuts and lattice-free cuts in the extended space to the effect of adding the same types of cuts in the original space. We observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. Finally, we also discuss extended formulations of mixed-integer programs obtained by replacing integral variables by binary variables and compare the effect of split cuts applied to these extended formulations versus split cuts applied to the original formulation.
Bio
Dr. Sanjeeb Dash is a member of the research staff at the Mathematical Sciences Department of the IBM T. J. Watson Research Center. He works on both theoretical and practical aspects of Discrete Optimization. The focus of his research is Integer Programming and Linear Programming. He has co-authored the QSopt and QSopt_ex linear programming solvers and is an Area Editor of the journal Mathematical Programming Computation, and Associate Editor for a number of other journals including Operations Research and INFORMS Journal on Computing.