Invited speakers

print
preview

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.

 

preview

Xiaotie Deng, Shanghai Jiaotong University

Constructive Output of Existentially Proved Structure in Combinatorics

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.

 

preview

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.

Bernard Ries received his PhD in 2007 from the Swiss Federal Institute of Technology in Lausanne. In 2008-2009 he was a postdoctoral research fellow at Columbia University (US) before he moved to Warwick University (UK) as an assistant professor. From 2010 to 2015, he was an associate professor at the University Paris Dauphine (France) and in August 2015 he was hired as an associate professor at the University of Fribourg (Switzerland). He has been an invited researcher at several universities including Haifa University (Israel), University of Montreal (Canada), Memorial University of Newfoundland (Canada), University of Warsaw (Poland), Durham University (UK), Kadir Has University (Turkey), Gdansk University of Technology (Poland). His research interests are structural and algorithmic graph theory, complexity theory and combinatorial optimisation.

 

preview Gerhard J. Woeginger (EURO Plenary), RWTH Aachen

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.

Gerhard Woeginger is a professor at RWTH Aachen, where he chairs the algorithmics and complexity group in the department of computer science. His research interests lie in the intersection area of Operations Research, Theoretical Computer Science, and Discrete Mathematics.  Woeginger was program chair of the European Conference on Operational Research (EURO-2009), the International Computer Science Symposium in Russia (CSR-2016), and of several other conferences. He received a Humboldt Research Award in 2011, and he was elected to the Academia Europaea in 2014.