Research Field

Discrete mathematics has its origins at the intersection of mathematics and computer science, but in recent decades, it has been established as an independent field of study. Its models, methods, tools, and algorithms are at the core of key application fields such as transportation, logistics, telecommunications, bioinformatics, and image processing, to mention just a few.

Modern methods of discrete mathematics are remarkably diverse and flexible: Their spectrum includes algorithmic, randomized, probabilistic, approximative, geometric, topological, algebraic, and optimization methods. The combination and interaction of such tools has enormously increased the power and the range of combinatorial reasoning in recent years, especially for applications in computer science, optimization, and operations research.

Berlin Research Groups

Over the past twenty years, Berlin has developed into an internationally visible and acclaimed place for graduate education in discrete mathematics and optimization. This is due not only to the activities of individual faculty members and groups, but even more so to the joint activities of the research groups in discrete mathematics and optimization at FU, HU, TU, and ZIB. These include the RTGs Algorithmic Discrete Mathematics (1990-1998) and Combinatorics, Geometry and Computation (2000-2005), Methods for Discrete Structures (2006-2016), and Facets of Complexity (2018- ) with their colloquia, block courses, and summer schools.

In the following, we give some prominent examples of research areas in discrete mathematics and combinatorial optimization that we are working on. Naturally, these different areas are strongly interrelated, and many interesting research questions have connections to several of these areas.

Graphs are fundamental building blocks in many areas of discrete mathematics and theoretical computer science; important and interesting concepts include planarity, minor theory, orientation, extremal properties, partial orders and network optimization (Felsner). Within the past years, also due to several new faculty members, special emphasis has been laid on the area of approximation and online algorithms for hard problems in discrete optimization (Skutella). In combinatorial optimization, substantial effort is being put into the development of mathematical tools and algorithms (such as network flow algorithms and integer programming techniques) to the point where their impact can be seen on genuine industrial applications. Much of the Berlin effort in this direction is based at ZIB (Borndörfer, Koch) and in the Innovation Area “Mathematics for Metropolitan Infrastructure" of MATHEON and ECMath. Similarly, graph algorithms, optimization techniques and the theory of discrete dynamical systems such as Boolean networks are the basis for the development of efficient modeling and analysis methods for biological systems such as molecular interaction networks in a cell (Bockmayr, Siebert).

Discrete and combinatorial geometry is a broad field in which topological and algebraic methods have found striking applications to combinatorial problems (HaaseHenk, JoswigZiegler). The more computer science oriented field of computational geometry is particularly concerned with the complexity of algorithms for geometric problems (Rote, Mulzer). Algebraic complexity theory seeks to relate topics in computational complexity to algebraic concepts (Bürgisser). Extremal and probabilistic combinatorics are two thriving branches in current combinatorial research; they are strongly interrelated and influence each other in many ways (Szabó).

 

Basic Courses

The three Basic Courses in discrete mathematics, discrete optimization, and nonlinear optimization are independent. Each of them is designed to cover basic foundations of the field, in view of current research directions pursued in Berlin.

The discrete combinatorics course treats basic structures and methods from the core areas of discrete mathematics, such as enumerative combinatorics, algebraic combinatorics, and graph theory – topics that are also of great importance in nearly all other parts of mathematics.

The discrete optimization course gives a solid understanding of the basic role of discrete optimization, models, methods, and consequences. The course presents both the deep theoretical consequences of discrete optimization models (in terms of duality theory, geometry, and polyhedra, for instance) and the immense practical importance of optimization tools in economic and industrial applications. 

Nonlinear optimization is an indispensable tool for dealing with real world problems, e.g. for identifying system parameters and/or for optimizing the performance of a technical or economical process. In the course we consider nonlinear differentiable optimization problems in finite dimensions. In a mixture of theoretical analysis and numerics we discuss necessary and sufficient optimality conditions for unconstrained and constrained problems. We develop algorithms for the numerical solution of these problems, study their convergence properties and use MATLAB to implement some of them.


Outline of the contents:

Combinatorics

◦ Basic counting problems

◦ Enumeration, generating functions

◦ Basic graph theory: graphs and hypergraphs

◦ Basic structure theory: posets and lattices

Discrete optimization

◦ Linear and integer programming

◦ Simplex algorithm, duality, geometry, ellipsoid method

◦ LP-based methods (cutting plane approaches, branch and bound)

◦ Matchings, matroids

◦ Approximation algorithms

Nonlinear optimization 

◦ Nonlinear optimization problems, modeling

◦ Optimality conditions

◦ Numerical methods 

◦ Nonsmooth optimization

◦ Interior point methods

 

Spectrum of Advanced Courses

Topics for typical advanced courses include Extremal Combinatorics, Probabilistic Methods, Order Theory, Designs and Codes, Algebraic Combinatorics, Topological Methods; Combinatorial Algorithms, Approximation Algorithms, Online-Algorithms, Mechanism Design, Online Optimization, Scheduling, Periodic Timetabling and Passenger Routing, Integer and Mixed-Integer Programming, Convex Optimization and Applications.