Skip to main content Skip to navigation

Network Optimisation

Network theory deals with the study of graphs as a description of relations between discrete objects. This very abstract and general notion includes for example the study of the World Wide Web, the Internet, social networks, networks in tele-communcications, or logistic networks in supply chain management.

Within this vast area, the research within DIMAP mainly focuses on Network optimisation which deals with solving certain problems on networks, like e.g. the Traveling Salesperson problem, facility location, shortest path problems, cut problems, or flow problems. Another aspect are network design problems where the output of the problem is a network.

We approach problems of this type from a theoretical perspective by designing approximation algorithms for them, i.e., algorithms that guarantee, both, polynomial running time and a certain solution quality, but also from a heuristic perspective where we aim at finding the optimum solution with the caveat that we cannot guarantee a polynomial running time anymore. See also Combinatorial Optimisation .

Sample publications: