Networks
Research themes
1. Approximate and exact network methods
In situations in which it is hard to compute optimal solutions exactly, one may resort to techniques that are close to optimal. More concretely, for the class of NP-complete problems, which are generally believed to be non-solvable in polynomial time, one could try to develop techniques that yield a solution that is at most a fixed percentage off the optimal value. A commonly applied and powerful approximation idea is to first consider a convex relaxation of the problem at hand, and then convert this into an integral solution. One major challenge lies in determining the class of network problems for which such relaxations work, also relying on the concept of convex programming hierarchies.
A second topic concerns techniques that focus on average case behavior of algorithms, rather than on worst-case behavior. A key question in this respect is which structural properties of real-world networks facilitate the development of algorithms that are fast for ``most” instances.
The projects related to this theme are:
- Citation networks and performance measures
- Algorithmic and combinatorial aspects of partition functions
- Evolutionary Algorithms for Treatment Planning in Radiotherapy
- TSP and other problems on point sets in thin subspaces
- Network Optimization under Strategic Behaviour and Data Uncertainties
- Decision making under uncertainty
- Hamilton cycles in sparse graphs
- Combinatorial Algorithms on Strings and Graphs
- Analysis of community detection algorithms in real-world and random graphs
- Geometric Optimization Problems with Time-Varying Input
- Extremal, algorithmic, and enumerative problems in graph theory
- Statistical mechanics of and on random graphs
- Emergence of heavy tails in stochastic networks
- Algorithms on strings and labelled graphs
- Network Design for Strategic Environments