INVITED SPEAKERS

INVITED SPEAKERS:

 Jon Lee, University of Michigan, USA

Recent algorithmic advances for maximum-entropy sampling

Abstract:The maximum-entropy sampling problem (MESP) is to select a subset, of given size s, from a set of correlated Gaussian random variables, so as to maximize the differential entropy. If C is the covariance matrix, then we are simply seeking to maximize the determinant of an order-s principal submatrix. A key application is for the contraction of an environmental-monitoring network. MESP sits within the intersection of optimization and data science, and so it has attracted a lot of recent attention. The problem is NP-hard, and there have been algorithmic attacks aimed at exact solution of moderate-sized instance for three decades. It is a fascinating problem from the perspective of integer nonlinear optimization, as it does not fit within a framework that is successfully attacked via available general-purpose paradigms. I will give a broad overview of algorithmic work, concentrating on the many useful techniques related to various convex relaxations.

Bio: Jon Lee obtained his Ph.D. at Cornell University. He has held long-term positions at Yale University, University of Kentucky, IBM Research, and New York University. Now at the University of Michigan, Jon is the G. Lawton and Louise G. Johnson Professor of Engineering and Professor of Industrial and Operations Engineering. He is author of “A First Course in Combinatorial Optimization” (Cambridge University Press), “A First Course in Linear Optimization” (Reex Press), and “Maximum-Entropy Sampling: Algorithms and Application” (with M. Fampa). Jon was the founding Managing Editor of the journal Discrete Optimization, and he is currently Editor-in-Chief of Mathematical Programming, Series A. Jon is an INFORMS Fellow, and he has received the INFORMS Computing Society Prize.

Petra Mutzel, Bonn University, Germany

Algorithmic Data Science

Abstract: The area of algorithmic data science offers new opportunities for researchers in the algorithmic and the optimization community. In this talk we will first survey four fundamental problems for analysing data. The basis for these problems are concepts for distance and similarity. We will discuss similarity concepts for graphs that are relevant for analysis tasks on graph data sets. These approaches are increasingly applied in the context of data analysis tools for systems with a network structure. Applications are, e.g., learning tasks in drug design, social network analysis, and geodesy.

Bio: Petra Mutzel is professor of Computational Analytics at the University of Bonn, where she is also the scientific director of the High Performance Computing and Analytics Lab at the Digital Science Center. Before she was professor at TU Dortmund University and at Vienna University of Technology. She received her Ph.D. in Computer Science at the University of Cologne in 1994, followed by a PostDoc position at the Max Planck Institute for Informatics in Saarbrücken. Her research focuses on algorithm engineering, algorithmic data analysis, and combinatorial optimization for graphs and networks. Currently, the main application areas are in cheminformatics, social and biological network analysis,  statistical physics, and geodesy. She is a member of the Steering Committees of ESA, ALENEX, and WALCOM, and Associate Editor of the ACM Journal on Experimental Algorithmics, Journal of Graph Algorithms and Applications (JGAA), and Mathematical Programming Computation (MPC).

Rekha R. Thomas, University of Washington, USA

  Graphical Designs

Bio: Rekha Thomas received a Ph.D. in Operations Research from Cornell University in 1994 under the supervision of Bernd Sturmfels.  This was followed by two postdoctoral positions, the first at the Cowles Foundation for Economics at Yale University and the second at the Konrad-Zuse-Zentrum for Informationstechnik in Berlin. She is currently the Walker Family Endowed Professor in Mathematics at the University of Washington in Seattle. Her research interests are in optimization and applied algebraic geometry.

Rico Zenklusen, ETH Zurich, Switzerland

Advances in Approximation Algorithms for Tree Augmentation

Abstract: Augmentation problems are a fundamental class of Network Design problems. The goal is to find a cheapest way to increase the (edge-)connectivity of a graph by adding edges among a given set of options. The Minimum Spanning Tree Problem is one of its most elementary examples, which can be interpreted as determining a cheapest way to increase the edge-connectivity of a graph from 0 to 1. The "next step", to increase from 1 to 2, leads to the heavily studied Tree Augmentation Problem, which is the focus of this talk. This talk has several goals, namely:
1) Providing a brief introduction to Tree Augmentation and some related problems.
2) Discussing relevant algorithmic techniques, including the Relative Greedy method and a new link to local search procedures.
3) Showing how these techniques can be leveraged to address a long-standing open question, namely how to obtain better-than-2 approximations for (Weighted) Tree Augmentation.

Bio: Rico Zenklusen is a Professor in the Mathematics Department at ETH Zurich, heading the Combinatorial Optimization Group. Prior to joining ETH Zurich, Rico was on the faculty of the Johns Hopkins University, before which he worked several years as a postdoc at MIT, and also shortly at EPFL. Rico holds a PhD from ETH Zurich and a master's degree from EPFL. His main research interests lie broadly in Combinatorial Optimization and its applications, ranging from foundational research related to polyhedra, (poly-)matroids, and submodular functions to industrial collaborations.