Prof. Anna Beliakova
Mathematics and statisticsTopology and Categorification
Information and Communication Technologies (ICTs), Mathematics and statistics
Mathematical optimisation, algorithmics
My research area is in the field of mathematical optimisation. The (further) development of effective algorithms for both NP-hard problems and polynomial solvable problems is of particular interest to me. It is my aim to develop practically efficient but, above all, exact algorithms, to implement them in terms of algorithm engineering and to evaluate them for use in relevant applications. I enjoy studying problems that have applications in the natural sciences, for instance in physics, but also in operations research. My work focuses on combinatorial optimisation, polyhedral combinatorics and graph algorithms.
An additional focus of my research is the further development of general methods in nonlinear optimisation, for example in binary constrained quadratic optimisation.
I am the head of a young researcher group in the Department of Computer Science at the University of Cologne within the framework of the German Research Foundation Emmy Noether Programme. The research topic for this project is the development of exact optimisation algorithms for problems in theoretical physics. Frequently, these algorithms can be applied to solving problems in other fields.
English, German, Italian
Liers, F.: On Combinatorial Optimization in Physics and Binary Quadratic Programming. Kumulative Habilitationsschrift. Universität zu Köln, 2010.
Liers, F., Pardella, G.: A Simple Max-Cut Algorithm for Planar Graphs. Erscheint in Computational Optimization and Applications.
Ghaddar, B., Anjos, M., Liers, F.: A Branch-and-Cut Algorithm Based on Semidefinite Programming for the Minimum k-Partition Problem. Erscheint in Annals of Operations Research.
Baumann, F., Buchheim, C., Liers, F.: Exact Bipartite Crossing Minimization under Tree Constraints. In: 9th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 6049, S. 118-128. Springer
Verlag, Berlin 2010.
Buchheim, C., Liers, F., Oswald, M.: Speeding up IP-based Algorithms for Constrained Quadratic 0-1 Optimization. In: Mathematical Programming B 124(1-2), 2010. S. 513-535.
Fanghänel, D., Liers, F.: A Fast Exact Algorithm for the Problem of Optimum Cooperation and the Structure of Its Solutions. In: Journal of Combinatorial Optimization 19(3), 2010. S. 369-393.
Buchheim, C., Liers, F., Oswald, M.: Local Cuts Revisited. In: Operations Research Letters 36(4), 2008. S. 430-433.
Pardella, G., Liers, F.: Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses. In: Physical Review E 78(5), 2008. S. 056705.
Liers, F. et al: Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut. In: New Optimization Algorithms in Physics, 2004. S. 47-68. Wiley-VCH.
I am the head of a young researcher group within the framework of the project funded by the Emmy Noether Programme. Working with one doctoral student, one postdoc, two student employees and additional Diplom-degree seeking students, I am studying optimisation problems that have applications in theoretical physics. The algorithms developed are also relevant to applications in operations research, for example in chip layout, or in frequency allocation in telecommunications. We begin by studying the basic problems using a graph theory or polyhedral approach. Using these results, we can then develop good, exact algorithms. Depending on the problem, this could be a matter of algorithms with polynomial running time or branch-and-bound and branch-and-cut (-and-price) algorithms. We would then make the implemented algorithms available via, for instance, a computer server. Frequently, these algorithms can be applied to solving problems in other fields. Currently, one of the things we are working on is an algorithm we developed to determine maximum cut in planar graphs to be used for chip layout in modern computer chips. This work is being carried out with experts in VLSI design.
In practice, there are fast algorithms for solving many linear combinatorial optimisation problems, such as algorithms for determining optimal linear orderings, optimal matchings, the shortest paths of a commercial traveller, etc. There are also relevant applications, though, in production planning, in visualisation or in biology, in which a nonlinear objective function must be optimised over a well-studied polytope. In this project, we are studying general solution methods for these problems. Our goal remains the same: to develop an exact algorithm. There are many things being developed, including more general separation routines, which can be used in a branch-and-cut algorithm without studying the underlying problem in detail using a polyhedral approach. This will provide both theoretical contributions to optimisation and indicate practical implementations. We are currently studying a robust network design problem that arises in industrial problems.
Union of German Mathematicians (DMV)
GI (German computer science society), and in the advisory council for university professors
Gesellschaft für Operations Research (German operations research society)
Mathematical Programming Society
Member of the committee to safeguard good scientific practice at the University of Cologne
Member of the scientific advisory board of the University of Cologne
You can only see the contact information of the academics in the database if you are a registered user of AcademiaNet.
Please register here
Please download the brochure "No more excuses" and read more about female experts in Europe, and about AcademiaNet.
Mathematics and statisticsTopology and Categorification
Mathematics and statisticsAlgebra, Representation Theory
Environment, Mathematics and statisticsbiogeochemistry, isotope geochemistry, soil science
Information and Communication Technologies (ICTs)Distributed systems