Invited speakers

Robert Bixby, Gurobi Optimization, Inc.

Progress in Linear and Mixed-Integer Programming

We will look at progress in Linear Programming (LP) and Mixed Integer Programming (MIP) software over the last 25 years.   As a result of this progress, modern LP codes are capable of robustly and efficiently solving instances with multiple millions of variables and constraints.
With these LP advances as a foundation, MIP provides the modeling framework and the key solution technology behind prescriptive analytics.  The performance improvements in MIP codes have been nothing short of remarkable, well beyond those of LP, and have transformed this technology into an out-of-the box tool with an almost unlimited range of real-world applications.

Dr. Robert Bixby has a BS in Industrial Engineering and Operations Research from the University of California, Berkeley (1968), and a PhD in Operations Research from Cornell University (1972). He has held numerous academic positions in USA and Germany. He is currently Noah Harding Professor Emeritus of Computational and Applied Mathematics at Rice University, and visiting Professor in the Department of Mathematics at Universität Erlangen.  He is also the co-founder (2008) and CEO of Gurobi Optimization..
Dr. Bixby has published over fifty journal articles, and is an acknowledged expert on the computational aspects of linear and integer programming. He has won several awards for his work in optimization. In 1997 he was elected to the National Academy of Engineering for his contributions to the theory and practice of optimization. In 2012 he was awarded an honorary doctorate in Mathematics from the University of Waterloo, Canada.

Xiaotie Deng, Shanghai Jiaotong University

Constructive Output of Existentially Proved Structure in Combinatorics

The Sperner's lemma, as a discrete version of the Brouwer’s fixed point theorem, has played a key role in our understanding of the computational complexity class PPAD, linking among the class, the 2 player’s Nash equilibrium computation, and solutions for various problems possessing existential combinatorial structures. Recent development in the closely related computational complexity class PPA shows a tie of the 2D Mobius band, the simplest non-orientable topological space, in shaping our understanding of the complete problem in PPA.
In this talk, we discuss recent results for different combinatorial problems that guarantee the existence of substructures for which finding a solution is PPA-complete.

Xiaotie Deng got his BSc from Tsinghua University, MSc from Chinese Academy of Sciences, and PhD from Stanford University. He is currently a Zhiyuan Chair Professor of Shanghai Jiaotong University. He taught in the past at University of Liverpool, City Universtiy of Hong Kong, and York University. Before that, he was an NSERC international fellow at Simon Fraser University.
Deng's current research focuses on algorithmic game theory, with applications to Internet Economics. His other works cover online algorithms, parallel algorithms, and combinatorial optimization. He is an ACM fellow for his contribution to the interface of algorithms and game theory.

Bernard Ries, University of Fribourg

On some graph modification problems

A typical graph modification problem aims to modify a graph G, via a small number of operations from a specified set~S, into some other graph H that has a certain desired property, which usually describes a certain graph class G to which H must belong. In this way a variety of classical graph-theoretic problems is captured. For instance, if only k vertex deletions are allowed and H must be an independent set or a clique, we obtain the Independent Set or Clique problem, respectively.

Now, instead of fixing a particular graph class G, we fix a certain graph parameter  π. That is, given a graph G, a set S of one or more graph operations and an integer k, we ask whether G can be transformed into a graph G' by using at most k operations from S, such that π(G') ≤ π(G)-d for some threshold d ≥ 0.  Such problems are called blocker problems, as the set of vertices or edges involved can be seen as ``blocking''  some desirable graph property (such as being colorable with only a few colors). Identifying the part of the graph responsible for a significant decrease of the parameter under consideration gives crucial information on the graph.

Blocker problems have been given much attention over the last few years. In this talk, I will give an overview of recent results on this topic.

Lower bound techniques for algorithmic problems

There is only a handful of tools for establishing lower bounds on the time complexity of algorithmic problems. For instance, 3-SUM-hardness (introduced by Gajentaan and Overmars) yields conditional quadratic lower bounds for a variety of problems in computational geometry. The All-Pairs-Shortest-Paths conjecture of Williams and Williams yields conditional cubic lower bounds for many natural problems in graph algorithms. The exponential time hypothesis (ETH) has become very popular in recent years.
The talk surveys some of these tools and provides a number of illustrating examples.