Nikhil Bansal

Title: Discrepancy and Combinatorial Optimization

Abstract: Discrepancy is a combinatorial property that is closely related to how well a fractional solution to a linear program can be rounded to an integral one. We will explore various techniques in discrepancy theory, and their applications to basic problems in combinatorial optimization. Some of the topics that we will cover include, rounding techniques based on random walks and linear algebra, Steinitz lemma and its use in integer programming, tools from convex geometry to show existence of and find integer points in convex bodies.

Bio

Nikhil Bansal is a researcher at CWI, Amsterdam and a professor in the department of mathematics and computer science at Eindhoven University of Technology. He did his Bachelors in Computer Science from IIT Mumbai (1999) and obtained his PhD from Carnegie Mellon University in 2003. He worked at the IBM T.J. Watson Research Center until 2011, where he also managed the Algorithms group. He is broadly interested in theoretical computer science with focus on the design and analysis of algorithms, and in related areas such as discrete mathematics, machine learning and queueing theory. He has received several best paper awards for his work including one at the FOCS 2011 conference. He is a recipient of NWO VIDI, TOP and VICI grants, and an ERC consolidator grant, and is currently an associate editor for Journal of the ACM and Mathematics of Operations Research.

Samuel Burer

Title: An Introduction to Semidefinite Programming for Combinatorial Optimization

Abstract: Semidefinite programming (SDP) is a powerful modeling technique that extends both linear and second-order cone programming. In this tutorial, we discuss the basics of SDP, including applications, duality, algorithms, and software. We'll also cover various SDP relaxation techniques for combinatorial optimization problems such as MaxCut and maxiumum stable set, which are classical "success stories" in this area. Finally, we'll explore the boundary of current research, especially in the area of mixed-integer nonlinear programming.

Bio

Sam Burer is George Daly Professor and Graduate Business Analytics Director in the Department of Management Sciences at the University of Iowa. He received his Ph.D. from the Georgia Institute of Technology, and his professional interests include optimization, operations research, management sciences, and analytics. His research has been supported by grants from the National Science Foundation, and he serves on the editorial boards of Management Science, Operations Research, and SIAM Journal on Optimization. He has also served as a Member of the Board of Directors of the INFORMS Computing Society and as a Council Member of the Mathematical Optimization Society.

João Gouveia

Title: Sums of Squares in Polynomial Optimization

Abstract: Polynomials offer an extremely general strong tool to encode optimization problems, both discrete and continuous. However polynomial optimization is in general hard, and for a long time it has been confined mostly to the realm of theoretical real algebraic geometry. The advent of efficient semidefinite programming a couple of decades ago, transformed what was a purely theoretical pursuit into a practical endeavor, and gave rise the development of general tools for approximating polynomial optimization problems. The most common of these approaches is perhaps the sum of squares approach, that relies on certifying non-negativity of polynomials by writing them as sums of squares of other polynomials, and that allows anyone to quickly obtain bounds for polynomial optimization problems. In these lectures, a quick overview of the theoretical foundations for these techniques will be given, as well as an overview of how can they be applied to bound a range of problems from diverse areas. Finally we will review some recent and ongoing developments in the field.

Bio

João Gouveia obtained his PhD from University of Washington in 2011, and has since been in the Department of Mathematics at the University of Coimbra, where he is currently an associate professor. His main interests lie at the intersection of optimization, algebraic geometry and convex geometry, but he is also usually involved in several applied industrial projects.